Pourquoi résoudre les finales d'échecs avec une pièce de plus a-t-il pris dix ans de plus ?

À cause de l'explosion combinatoire : la croissance rapide de la complexité d'un problème à mesure que ses données augmentent. En 2005, toutes les finales d'échecs à six pièces ou moins avaient été résolues, le résultat de chaque position en cas de jeu parfait étant consigné dans une « table de finales ». Ajouter une seule pièce a apporté tant de complexité combinatoire que la table à sept pièces a demandé dix ans de plus, et une table à huit pièces est jugée hors de portée. C'est aussi pour cela que les échecs, avec seulement 64 cases et 32 pièces, ne sont toujours pas un jeu résolu.

Le phénomène apparaît partout dès qu'on y regarde de près. Une grille de sudoku est un type particulier de carré latin, et à mesure que la grille grandit, l'explosion combinatoire limite les sudokus qu'on peut construire, analyser et résoudre. Même compter combien de carrés latins existent selon leur taille est un exemple classique de cette explosion.

La même explosion apparaît avec quelque chose d'aussi simple que des interrupteurs vrai/faux. Une seule variable booléenne a deux états possibles, mais chaque variable supplémentaire double ce nombre : deux variables donnent quatre états, trois en donnent huit, et n variables en donnent deux puissance n. Ce doublement s'accumule brutalement vite.

Cela apparaît même dans quelque chose d'aussi humain que de savoir qui doit parler à qui. Deux services n'ont besoin que d'un seul canal de communication ; en ajouter un troisième en nécessite trois ; un quatrième en nécessite six ; un cinquième, dix ; un sixième, quinze. On appelle souvent cette croissance « exponentielle », mais il s'agit en réalité d'une croissance polynomiale, plus lente mais tout aussi pénible, qui suit la même formule que le comptage du nombre de paires que l'on peut former dans un groupe.