Résoudre ce problème mathématique permettrait de s’accaparer tous les bitcoins existants

Certains affirment que P=NP reste la principale énigme des mathématiques aujourd’hui. Que ça soit le cas ou non, chacun s’accorde à dire qu’il regorge d’implications pratiques et même philosophiques. Il est revenu récemment sur le devant de la scène suite à une petite phrase de l’ingénieur en informatique théorique Scott Aaronson : “Si quelqu’un prouve P = NP, la première chose qu’il devrait faire, c’est voler les 200 milliards de dollars qui existent en bitcoin. La deuxième, c’est résoudre tous les autres Problèmes du Prix du Millénaire”.

Passons sur le fait que voler tous les bitcoins réduirait instantanément leur valeur à néant, et essayons de comprendre comment un scientifique tout à fait sérieux est capable de prononcer cette phrase sans sourciller.

Une expérience de pensée fascinante

Aujourd’hui, tout ordinateur fonctionne selon des principes formalisés par Alan Turing, le grand-père de l’informatique moderne. Résoudre un problème demande un certain temps, qui dépend de sa complexité et de la puissance de la machine : augmenter la complexité du problème, c’est augmenter le temps nécessaire pour que la machine puisse le résoudre. Ce problème est représenté par P dans l’équation ci-dessus. Au fur et à mesure qu’on augmente la difficulté du problème, le temps nécessaire pour le résoudre va augmenter de façon dite “polynomiale”, c’est à dire un nombre avec un coefficient et une puissance (comme 3 x ²) : on parle de temps polynomial.

En substance, cela signifie que le temps de résolution augmente plus vite que la complexité du problème. On peut donc potentiellement les résoudre en un temps raisonnable à l’échelle humaine, mais cela devient de moins en moins abordable au fur-et-à-mesure que la complexité augmente. Pour de nombreux problèmes, nous sommes capables de déterminer la solution en un temps polynomial. C’est le cas pour des problèmes relativement simples, comme trier une liste par ordre alphabétiques ou réaliser des séries d’opérations mathématiques.

Mais il existe aussi tout un tas de problèmes plus complexes, que nous ne sommes pas certains de pouvoir résoudre en un temps polynomial mais où on peut facilement vérifier si une solution donnée fonctionne: on les appelle les problèmes “NP“, pour “Nondeterministic Polynomial”. Un exemple très parlant de problème “NP” est le célèbre Rubik’s Cube. On peut aussi citer le jeu du sudoku. Ceux qui se sont déjà attaqués à des grilles de haut niveau savent à quel point la terminer peut être difficile… voire quasiment impossible dans une vie humaine, dans le cas de grilles gigantesques à plusieurs dizaines de lignes et colonnes .Mais une fois terminé, vous pouvez déterminer si votre grille est juste ou pas grâce à une méthode simple. Les problèmes NP sont des puzzles : il peuvent (ou pas) être résolus en un temps polynomial, mais il est facile de vérifier si l’image obtenue est valide ou non.

Mais il existe également une autre classe de problèmes, encore plus ardus. Prenez les échecs, par exemple. Non seulement le processus qui permet de trouver le meilleur coup à jouer est excessivement complexe, mais même le fait de vérifier si le coup joué est le bon est tout sauf évident ! Les échecs ne tiennent plus du puzzle, puisqu’on ne sait même pas immédiatement si on avance dans la meilleure direction possible. Pour avoir tous les détails, sans approximation ni concession, sur la terminologie des différentes classes de complexité, nous vous proposons ce topic stackexhange effrayant mais très sérieux.

Parfois, souvent par chance, on s’est rendu compte que des problèmes qu’on pensait à l’origine être “NP” sont en fait des problèmes “P”, dont on peut trouver la solution en un temps polynomial. C’est le cas pour la recherche des nombres premiers, par exemple. Mais cela a mené à l’émergence d’une nouvelle question : et si les problèmes “NP” n’étaient en fait que des problèmes “P” pour lesquels nous n’avons pas trouvé la “bonne méthode” ?
C’est là toute l’essence du problème. Les problèmes NP sont-ils vraiment plus difficiles que les problèmes P ? Existe-t-il une façon “simple” (c’est à dire réalisable en un temps polynomial par un ordinateur) de résoudre tous les problèmes NP ? Ou en d’autres termes : est-ce que le fait de pouvoir reconnaître rapidement la bonne réponse si on nous la présente signifie qu’il existe une manière simple de la trouver à partir du point de départ?

P = NP ou la solution au problème de la recherche de solutions

Ce raisonnement peut paraître sinueux, mais répondre une bonne fois pour toutes à la question “P = NP ?” concerne la nature même de la recherche de solutions dans un ensemble exponentiel de possibilités. Ce qu’on cherche avec ce problème du Millénaire, c’est une méthode universelle de recherche de solutions pour ces problèmes “NP”. S’il était un jour vérifié que P = NP (ce qui est tout sauf acquis), les implications seraient tout simplement démentes. L’une d’elles a donné lieu à la phrase de Scott Aaronson citée plus haut.

Aujourd’hui, toute notre cryptographie ou presque s’appuie sur principe de base: générer des clés et autres jetons quasiment impossible à cracker (ce qui revient à trouver une solution au problème) en un temps polynomial, mais vérifiable en deux temps, trois mouvements pour authentifier ou valider une transaction. Or, le principe de la blockchain est intimement lié à ces concepts : si, effectivement, P = NP, alors cela signifie qu’il existe une méthode simple (c’est à dire réalisable rapidement par un ordinateur) pour miner efficacement des cryptomonnaies comme le bitcoin, par exemple. De quoi devenir immensément riche.

Mais pas seulement : si P = NP, il serait également facile de trouver des solutions à tout un tas d’autres problèmes comme celui du voyageur de commerce, ou celui qui a été posé aux candidats du GTOC de cette année. A l’heure actuelle, on se contente d’approximer la véritable réponse à ce genre de problèmes en usant d’ingéniosité et de force brute, c’est à dire en faisant tester un maximum de solutions à un ordinateur… Un peu comme les premiers ordinateurs capables de jouer aux échecs, qui calculaient autant de coups que possible pour choisir le meilleur – mais sans certitude que le meilleur coup se trouvait parmi ceux testés. Une méthode qui se révèle particulièrement inefficace puisque le temps nécessaire explose dès qu’on augmente légèrement la complexité.

Mais tout ne serait pas rose si quelqu’un prouvait que P = NP : cela équivaudrait aussi à dire qu’il existe une solution “simple” pour cracker tout mot de passe, par exemple. Il existe tant de possibilités liées à la démonstration de cette hypothèse que cela en donne la migraine : comme le précise Aaronson, la démonstration de P = NP permettrait certainement de résoudre les autres problèmes du millénaire dans la foulée – en même temps qu’une foule d’autres problèmes scientifiques, logistiques, conceptuels… Un concept bien résumé sur son blog :

Si P=NP, le monde serait très différent de celui que l’on pense qu’il est. Il n’y aurait […] aucun écart fondamental entre résoudre un problème et reconnaître la solution une fois qu’elle est trouvée. Tous ceux capables d’apprécier une symphonie seraient Mozart; tous ceux capable de suivre un argument point par point seraient Gauss; tous ceux capables de reconnaître une bonne stratégie d’investissement seraient Warren Buffet

Aujourd’hui, nous sommes encore à des années-lumières de trouver une démonstration, et nombre de scientifiques considèrent même ce postulat comme indémontrable, car faux. Mais tous admettent qu’il sera impossible d’en avoir le cœur net avant l’émergence d’une grande idée, capable de révolutionner l’étude de cette théorie.

Pour trouver de la documentation plus précise sur l’hypothèse P=NP ou la théorie de la complexité , voici quelques liens annexes :

–Deux articles très complets qui expliquent très bien le problème : ici et là

–Un topic où la terminologie précise de l’hypothèse est discutée rigoureusement, sans raccourcis

–Le fascinant blog de Scott Aaronson

🟣 Pour ne manquer aucune news sur le Journal du Geek, abonnez-vous sur Google Actualités. Et si vous nous adorez, on a une newsletter tous les matins.