explosión combinatoria
En matemáticas , una explosión combinatoria es el rápido crecimiento de la complejidad de un problema debido a cómo la combinatoria del problema se ve afectada por la entrada, las restricciones y los límites del problema. La explosión combinatoria se usa a veces para justificar la intratabilidad de ciertos problemas. [1] [2] Los ejemplos de tales problemas incluyen ciertas funciones matemáticas , el análisis de algunos acertijos y juegos, y algunos ejemplos patológicos que pueden modelarse como la función de Ackermann .
Un cuadrado latino de orden n es un arreglo de n × n con entradas de un conjunto de n elementos con la propiedad de que cada elemento del conjunto aparece exactamente una vez en cada fila y cada columna del arreglo. Un ejemplo de un cuadrado latino de orden tres viene dado por,
Un ejemplo común de un cuadrado latino sería un Sudoku completo . [3] Un cuadrado latino es un objeto combinatorio (a diferencia de un objeto algebraico) ya que solo importa la disposición de las entradas y no lo que realmente son las entradas. El número de cuadrados latinos en función del orden (independiente del conjunto del que se extraen las entradas) (secuencia A002860 en la OEIS ) proporciona un ejemplo de explosión combinatoria como se ilustra en la siguiente tabla.
Una explosión combinatoria también puede ocurrir en algunos rompecabezas que se juegan en una cuadrícula, como el Sudoku. [2] Un Sudoku es un tipo de cuadrado latino con la propiedad adicional de que cada elemento aparece exactamente una vez en subsecciones de tamaño √ n × √ n (llamadas cajas ). La explosión combinatoria ocurre a medida que n aumenta, creando límites a las propiedades de Sudokus que se pueden construir, analizar y resolver, como se ilustra en la siguiente tabla.
Un ejemplo de un juego en el que la complejidad combinatoria conduce a un límite de resolución es la resolución de ajedrez (un juego con 64 casillas y 32 piezas). El ajedrez no es un juego resuelto . En 2005 se resolvieron todos los finales de partidas de ajedrez con seis piezas o menos, mostrando el resultado de cada posición si se juega perfectamente. Se necesitaron diez años más para completar la base de la mesa con una pieza de ajedrez más, completando así una base de mesa de 7 piezas. Agregar una pieza más a un final de ajedrez (haciendo así una base de mesa de 8 piezas) se considera intratable debido a la complejidad combinatoria adicional. [9] [10]
Además, la posibilidad de resolver juegos de ajedrez más grandes se vuelve más difícil a medida que aumenta el tamaño del tablero, como en las variantes de ajedrez grandes y el ajedrez infinito . [11]
