Pourquoi certains casse-têtes se vérifient-ils vite mais, a priori, se résolvent-ils lentement ?

Certains casse-têtes ont une drôle de double personnalité : vérifier une réponse terminée est instantané, mais trouver cette réponse au départ peut être terriblement lent. Le Sudoku en est l'exemple classique. Si quelqu'un te donne une grille complétée, tu peux confirmer qu'elle est correcte en quelques secondes, il suffit de parcourir chaque ligne, colonne et bloc. Mais le problème général de résoudre des grilles de Sudoku de plus en plus grandes est connu pour être NP-complet, ce qui veut dire qu'il appartient à la classe des problèmes les plus difficiles dont les solutions peuvent être vérifiées rapidement, sans aucun raccourci connu pour les trouver.

Des algorithmes comme le retour sur trace par force brute arrivent à résoudre un Sudoku classique 9x9 assez efficacement, mais à mesure que la grille grandit, une explosion combinatoire se déclenche, et le nombre de possibilités à vérifier devient incontrôlable. C'est le trait caractéristique des problèmes NP-complets en général : même si une solution peut être vérifiée rapidement, il n'existe aucun moyen connu d'en trouver une rapidement, et le temps requis par tout algorithme connu augmente très vite avec la taille du problème.

Savoir si c'est une loi permanente des mathématiques ou juste un manque d'ingéniosité de notre part, c'est un grand problème non résolu de l'informatique théorique, appelé le problème P contre NP. Il demande, en substance, si tout problème dont la réponse peut être vérifiée rapidement peut aussi être résolu rapidement. Personne ne le sait. Il fait partie des sept problèmes du prix du millénaire, chacun doté d'un million de dollars pour la première solution correcte.

Le soupçon que vérifier et résoudre sont deux tâches fondamentalement différentes remonte plus loin qu'on ne le croirait. En 1955, le mathématicien John Nash a écrit une lettre à l'agence de sécurité nationale américaine, spéculant que casser un code suffisamment complexe devrait prendre un temps croissant de façon exponentielle avec la longueur de la clé, Comme une clé proposée se vérifie rapidement, prouver que Nash avait raison impliquerait ce qu'on appelle aujourd'hui P ≠ NP. Personne n'y est encore parvenu.