P = NP : vérifier une solution, est-ce déjà savoir la trouver ?

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Aujourd'hui, on démarre sur les chapeaux de roue avec une plongée vraiment vertigineuse pour toutes les personnes qui nous écoutent.

Intervenant 20:10

Ah ça c'est clair, je suis ravie d'être là pour décortiquer ça avec toi.

Intervenant 10:14

Alors, il faut s'imaginer un peu la scène, on est en 2007 et une célèbre entreprise japonaise de jouets, Takara Tomy, met 2 millions de dollars sur la table.

Intervenant 20:24

2 millions en liquide.

Intervenant 10:27

Ouais, rien que ça. Et la récompense, c'est pour quiconque parviendrait à résoudre un simple puzzle de 256 pièces. Un truc appelé Eternity 2. Pendant trois ans, des passionnés de toute la planète se jettent dessus. Et 3 ans plus tard, personne.

Intervenant 20:44

Zéro gagnant.

Intervenant 10:45

Pas un seul. L'argent n'a jamais été réclamé. Et derrière cet échec cuisant, avec pourtant toute la puissance de calculs modernes mobilisés, se cache en fait l'une des plus grandes énigmes de l'humanité. Un monument intellectuel qui tient la communauté scientifique en haleine depuis plus de 40 ans.

Intervenant 21:03

C'est fou ! Et pour vraiment mesurer l'ampleur de ce monument, faut quand même rappeler que ce mystère fait partie des 7 problèmes du prix du

Intervenant 11:09

millénaire.

Intervenant 21:11

Ceux posés par l'Institut Klee en l'an 2000. 7 énigmes fondamentales avec 1 million de dollars pour chaque démonstration. Et celles qui nous intéressent pour cette exploration, elles se résument à une équation d'une simplicité trompeuse. 4 petits caractères. P

Intervenant 11:24

égale NP.

Intervenant 21:26

Voilà. P égale NP.

Intervenant 11:28

Forcément, quand on croise cette formule, il y a toujours la bonne vieille blague de lycéen qui sort, genre P égal NP, c'est facile, il suffit que N soit égal à

Intervenant 21:36

1. Ou alors la personne un peu plus pointilleuse au fond de la classe qui va dire, hé, on n'oublie pas que ça marche très bien si P égal 0.

Intervenant 11:43

C'est de bonne guerre. Mais bon, la mission de notre analyse aujourd'hui, c'est vraiment de dépasser ces petites blagues pour palper la signification profonde de ces lettres, comprendre ce que nos ordinateurs peuvent faire et surtout, ce qu'ils ne pourront peut-être jamais faire.

Intervenant 21:58

Exactement, on touche aux limites même de l'informatique et de la pensée logique.

Intervenant 12:02

Du coup, pour rendre ça bien digeste pour le public, reprenons notre fameux puzzle japonais, c'est le cobaye parfait.

Intervenant 22:08

Très bon exemple,

Intervenant 12:09

ouais. On a une grille de 16 cases par 16, donc 256 emplacements. On a 256 pièces carrées et sur chaque côté, il y a un motif coloré, une sorte de triangle.

Intervenant 22:18

La règle est super basique.

Intervenant 12:20

Mais oui, c'est enfantin ! Pour peser deux pièces côte à côte, leurs couleurs doivent juste correspondre. N'importe quel puzzle de 1000 pièces, avec un ciel bleu tout uni, ça se résout avec un peu de patience.

Intervenant 22:31

C'est vrai.

Intervenant 12:32

Alors décortiquons tout ça. Avec toute la puissance de calcul des ordinateurs de la planète, comment un simple puzzle de 256 pièces a-t-il pu résister ? Pourquoi ne pas juste faire tester toutes les combinaisons par une machine ?

Intervenant 22:45

C'est là que la combinatoire devient un monstre absolu. Faut décortiquer la mécanique de l'explosion exponentielle. Sur la première case, l'ordinateur peut essayer 256 pièces. Pour la deuxième case, il lui reste 255

Intervenant 12:58

choix,

Intervenant 23:00

puis 254, et ainsi de suite. C'est ce qu'on appelle la factorielle de 256. Mais en plus, chaque pièce est carrée, donc elle a 4 sens de rotation possibles. Le calcul final du nombre d'arrangements, c'est la factorielle de 256, multipliée par 4 à la puissance 256. Attends,

Intervenant 13:19

le résultat, ça donne un nombre avec plus de 600 chiffres, c'est bien ça ?

Intervenant 23:23

Absolument, plus de 600 chiffres. Pour donner une échelle à ceux qui nous écoutent, le nombre d'atomes dans l'univers observable tout entier s'aplafonne à environ 80 chiffres.

Intervenant 13:33

Waouh ! 80 chiffres contre 600 !