« P = NP ? Équation facile, N = 1 », dira l’élève de lycée. « Tu oublies P = 0 », ajoutera sa camarade plus rigoureuse. La réalité est un peu plus compliquée. Avant d’en comprendre la signification précise, essayons d’en percevoir l’idée au travers d’un exemple.
Résoudre un puzzle
En 2007, la société de jeu japonaise Takara Tomy Co. a proposé un puzzle de deux cent cinquante-six pièces carrées, à déposer dans un carré de taille 16 × 16. Chaque côté d’une pièce possède une couleur, celle du triangle qui s’appuie sur ce côté (comme sur l’exemple ci-dessous, avec neuf pièces sur la figure à gauche). On doit remplir le puzzle en respectant une unique contrainte : on ne peut déposer deux pièces côte à côte que si les deux côtés qui se touchent ont la même couleur (le puzzle est résolu sur la figure à droite).
Les neuf pièces du puzzle.
Le puzzle résolu.
Un puzzle de deux cent cinquante-six pièces, c’est facile à résoudre ? Pas tant que ça : la société de jeu offrait deux millions de dollars à la première personne à trouver une solution au puzzle avant fin 2010. De nombreuses équipes de programmeurs, chercheurs, étudiants, ont essayé… en vain ! Personne n’a trouvé de solution ...
Lire la suite