Em matemática, uma explosão combinatória é o rápido crescimento da complexidade de um problema devido a como a combinatória do problema é afetada pelos seus inputs, restrições e limites. A explosão combinatória às vezes é usada para justificar a intratabilidade de certos problemas. [1] [2] Exemplos incluem certas funções matemáticas, a análise de alguns quebra-cabeças e jogos e alguns exemplos que podem ser modelados como a função de Ackermann.
Um quadrado latino de ordem n é um quadrado n × n com entradas de um conjunto de n elementos com a propriedade de que cada elemento do conjunto ocorra exatamente uma vez em cada linha e cada coluna do quadrado.
Um exemplo comum de um quadrado latino é um quebra-cabeça Sudoku completo. [3] Um quadrado latino é um objeto combinatório (em oposição a um objeto algébrico), pois apenas o arranjo das entradas importa e não o que as entradas realmente são. O número de quadrados latinos em função da ordem fornece um exemplo de explosão combinatória conforme ilustrado na tabela abaixo.
| n | O número de quadrados latinos de ordem 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 |
A explosão combinatória pode ocorrer em ambientes computacionais de maneira análoga ao espaço multidimensional. Imagine um sistema simples com apenas uma variável, uma booleana chamada A. O sistema possui dois estados possíveis, A = verdadeiro ou A = falso. Adicionar outra variável booleana B dará ao sistema quatro estados possíveis, A = verdadeiro e B = verdadeiro, A = verdadeiro e B = falso, A = falso e B = verdadeiro, A = falso e B = falso. Um sistema com n booleanos tem 2n estados possíveis, enquanto um sistema de n variáveis, cada uma com Z valores permitidos, terá Z n estados possíveis.