Explosión combinatoria

En matemáticas, una explosión combinatoria consiste en el crecimiento muy rápido de la complejidad de un problema debido a cómo se ve afectado por las condiciones iniciales, restricciones y límites del propio problema. La explosión combinatoria se utiliza a veces para justificar la intrazabilidad de ciertos problemas.​​ Hay muchos ejemplos de tales problemas, que incluyen ciertas funciones, el análisis de algunos rompecabezas y juegos y algunos ejemplos patológicos que pueden ser modelizados, como la Función de Ackermann.

Ejemplos

Cuadrados latinos

Un cuadrado latino de orden n es una matriz n × n cuyos elementos pertenecen a un conjunto de n elementos con la propiedad que cada elemento del conjunto aparece sólo una vez en cada fila y cada columna de la propia matriz. El siguiente es un ejemplo de cuadrado latino de orden tres:

1	2	3
2	3	1
3	1	2

Otro ejemplo muy común de cuadrado latino sería un puzle sudoku completo.​ Un cuadrado latino es un objeto combinatorio (como opuesto a un objeto algebraico) donde lo único que importa es la disposición de sus elementos y no lo que sus elementos, en esencia, son. El número de cuadrados latinos es una función de su orden, independientemente del conjunto del que se obtienen sus elementos. La sucesión A002860 del índice OEIS es un ejemplo de explosión combinatoria, en relación con los cuadrados latinos. Viene ilustrado por la siguiente tabla:

n	El número de cuadrados latinos de orden n
1	1
2	2
3	12
4	576
5	161,280
6	812,851,200
7	61,479,419,904,000
8	108,776,032,459,082,956,800
9	5,524,751,496,156,892,842,531,225,600
10	9,982,437,658,213,039,871,725,064,756,920,320,000
11	776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000

Sudoku

También ocurren explosiones combinatorias en algunos puzles dispuestos en forma matricial, como los sudokus. Un sudoku es un tipo de cuadrado latino con la propiedad adicional que cada elemento ocurre también sólo una vez en sub-secciones de medida √n×√n (llamadas cajas). La explosión combinatoria aparece a medida que aumenta n, creando límites prácticos a las propiedades de los sudokus que se pueden construir, analizar y solucionar, como se muestra en la siguiente tabla:

n	El número de sudokus de orden n (cajas de tamaño √n×√n)	El número de cuadrados latinos de ordenar n(para comparación)
1	1	1
4	288​	576
9	6,670,903,752,021,072,936,960​	5,524,751,496,156,892,842,531,225,600
16	7098596000000000000♠5.96×1098 (estimado)​	—
25	9000000000000000000♠4.36×10308 (estimado)​	—
(n = 9 es el generalmente jugó 9×9 Sudoku. El rompecabezas no incluye verjas donde √n es irracional.)

Juegos

Un ejemplo en un juego donde la complejidad combinatoria conduce a un límite para su solución es el  es en solucionar ajedrez (un juego con 64 plazas y 32 piezas). Ajedrecístico no es un juego solucionado. En 2005 todos finales de juego ajedrecísticos con seis piezas o menos estuvo solucionado, mostrando el resultado de cada posición si jugó perfectamente. Tome diez más años para completar el tablebase con uno más el trebejo añadió, por ello completando un 7-pieza tablebase. Añadiendo un más pieza a un final ajedrecístico (así haciendo un 8-pieza tablebase) está considerado intratable debido al añadido combinatorial complejidad.​​

Enlaces externos

• Esta obra contiene una traducción derivada de «Combinatorial explosion» de Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.

• Datos: Q2668364