Passer au contenu

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

“P = NP”; si cette petite équation ne paye pas de mine, il s’agit pourtant de l’un des Problèmes du Prix du Millénaire, une liste de sept problèmes mathématiques majeurs. Le résoudre aurait des implications très fortes à de nombreux niveaux. Parmi elles : la mort du concept du blockchain tel qu’on le connaît.

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

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.

30 commentaires
  1. J’ai l’impression que P=NP n’a rien d’une hypothèse mais simplement un raccourci pour dire qu’une solution existe pour un problème donné. Trouver comment résoudre un problème ne veux pas dire pouvoir résoudre tous les problèmes de l’univers, ca n’a pas de sens.

  2. “essayons de comprendre comment un scientifique tout à fait sérieux est capable de prononcer cette phrase sans sourciller”

    Etant donné que vous en avez fait l’accroche de votre article, et que jdg ne doit pas être le seul a l’avoir fait, l’objectif du dit scientifique semble tout à fait atteint … on parle de lui !

  3. Si si, ça a du sens (mais un peu difficile à comprendre). L’hypothèse “P=NP” signifie que les problèmes pour lesquels on est capable de vérifier si une solution déjà calculée est valide sont aussi des problèmes pour lesquels on est capable de trouver la solution directement. Si cette hypothèse est fausse, cela signifie qu’il existe des problèmes (qu’on appelle NP-Complets, l’article ne les mentionne pas) pour lesquels on est capable de vérifier rapidement la validité d’une solution déjà calculée, mais on n’est pas capable de calculer directement la solution (du moins pas en un temps raisonnable).

  4. “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…”

    C’est un peu mélangé, tout ça. Ce qui manque dans cet article (à part la mention des problèmes NP-Complets), c’est le fait que la théorie de la complexité algorithmique manipule essentiellement des problèmes de décision (réponse en “oui” ou “non”), alors que l’industrie considère essentiellement des problèmes d’optimisation (on cherche la meilleure solution possible). Les complexités de ces deux types de problèmes sont liées (c’est ce qui fait que la théorie de la complexité n’est pas qu’un jouet théorique sans application), mais ce qu’on veut faire en général d’un point de vue appliqué, c’est résoudre des problèmes d’optimisation NP-Difficiles.

    Et là, effectivement, on a deux solutions. Soit on utilise une force brute, qui certes a un temps de calcul au pire exponentiel, mais qu’on peut essayer de contenir par des astuces notamment mathématiques, et qui vise donc à trouver l’optimal, soit on renonce à l’optimalité pour garder une rapidité d’exécution, auquel cas on obtient effectivement une solution approchée. Le choix dépend de l’usage et du contexte. Mais tel que c’est rédigé, on a l’impression qu’on renonce en même temps à la rapidité de calcul et à la valeur de la solution. Ce serait plutôt bête de faire ça…

  5. Le fait que ce soit de la biométrie ou de la voix ne change rien, ça reste un vecteur de bits. Donc le problème.

    Et pour le « quelques secondes pour casser du RSA » avec un ordinateur quantique, ça implique d’avoir les bons algorithmes et plein d’autres trucs qu’on a pas actuellement je crois

  6. Si tu résous le problème de NP-completude par l’affirmative (P=NP) alors tu ne résous en effet pas tous les problèmes de l’univers, mais tu résous tous ceux qui sont des problèmes NP-complets. Et tu les résous d’un seul coup, tous ! Et il y en a des centaines, et des centaines, et des centaines. Ça fourrait probablement tous les scientifiques de mon labo temporairement au chômage car ils bossent tous sur des problèmes qui seraient résolus.

  7. C’est marrant de voir le JDG pondre un article sur ce problème très spécialisé. Mais c’est agréable en tous cas, car bien rédigé alors que le sujet est loin d’etre évident

  8. Merci pour ce bon article! Sujet complexe mais simple a lire et bien sourcé. On en voudrait des comme ça tous les jours!

  9. Oui, je me faisais la même réflexion. Compte tenu de la difficulté du sujet, je trouve l’article assez juste. Ça fait plaisir !

  10. Je me suis souvent fait la réflexion, et je ne suis pas sûr qu’on mette directement à la poubelle tous les travaux de recherche opérationnelle (qui est le premier domaine concerné). Après tout, même si un problème NP-Complet appartient finalement à P, tu imagines la tête du polynôme de sa complexité ? Entre le degré et la constante, on a toutes les chances d’avoir un algorithme strictement inexploitable concrètement.

  11. C’est intéressant d’ailleurs de constater que la question des machines quantiques est très visible médiatiquement, alors que les algorithmes quantiques ne sont quasiment jamais évoqués. Et la production scientifique me semble encore assez marginale (en même temps, de ce que j’en ai vu, ça rigole pas en terme de niveau scientifique). Pourtant, une machine sans algorithme…

  12. Par contre, il semblerait qu’il existe un algorithme quantique pour la factorisation de grands nombres en facteurs premiers. Pour casser RSA, c’est une étape incontournable…

  13. Bonjour à tous,
    À mon avis je ne suis pas d’accord sur la notation P=NP.
    Car si on prend comme exemple de Puzle c’est faire monté une photo correcte apartir de plusieurs photos.
    Donc si on note P=photo.
    Donc On ne peut pas noté que la puzle “portion de la photo” comme étant P. Cest vrai une photo mais il n’est egale à P: «n sous groupe est un groupe est sous espace vectoriel est espace vectoriel».Et par conséquence on ne peut pas admettre l’equation P=NP d’ une façon génèrale mais peut etre une solution particulier.
    Mais ma suggestion c’est de prêférable d’ecrire l’equation sous forme matricielle:
    Pn=arang(Pij).
    Avec i et j des nombres compris entre 1 et le nombre totale de puzles qu’on peut noter par exemple:q.
    Et donc n varie de zero à (q)² 
    Le nombre de photos qu’on peut avoir à partir de des arangements des Pij est q² et sur ces q² photos il y a une unique photo correcte noté Pc.
    Questions sur le temps quelle est le chemin le plus cours à suivre aprés avoir déterminer la démarche et quelle sont les facteurs et paramettre à mettre en évidence ou à prendre en considération pour réduire le temps d’aboutir à Pc.
    Une autre notation à ne pas confondre Pc=f(t) fonction de temps.mai plus tot il est de préferable de noté T(Pc)= f(t) avec T c’est le temps à mettre pour aboutir à Pc. 
    Par ailleurs je ne suis pas d’accord sur «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.» 
    L’ ecart réside dans le temps T
    …..
    Salutations

  14. le soucis est qu il y a confusion entre le blockchain et la facon de communiquer.
    Le fait de résoudre P=NP n’impactera pas tant que cela le bitcoin.
    Pourquoi ? déjç parcequ”on ne peut pas farmer a l infini, et qu’il faut donc retirer ce qui a déjà été farmé.
    Ensuite, la sécurité du blockchain n est pas son cryptage, mais le fait que l information est 1) extrêmement répartie et 2) c e n est pas le résultat qui est réparti mais la facon de l obtenir (dans un block chain on ne sait pas qu on a 2 euros, on sait qu on a farme 1 euros a un instant donne, puis 1 euros a un autre instant)

    De fait meme en cassant le chifrrage et en farmant n importe quoi, les blockchain permettraient de savoir ce qui a ete effectue en vrai de ce qui a ete cassé.

  15. en plus je pense qu il y a un socuis de compréhension. il a été démontré qu on ne peut pas démontrer tout ce qui existe dans un ensemble si on fait parti d el ‘ensemble. de fait , on ne peut pas tout démontrer sur les problèmes de l ‘univers puisque on en fait parti.
    Par contre, on pourra montrer que tout algorithme, quelque soit sa complexit, peut se résupmer a des algorythmes  simples

  16. Heu… Je ne suis pas sûr de comprendre l’exemple du puzzle. En tous cas, l’écriture P=NP est bien la bonne puisque P et NP sont des ensembles, dont les éléments sont des problèmes. Noter P=NP est donc parfaitement valide.

  17. Bonjour @mbinax,

    Pour proposer une réponse, il faut d’abord publier les résultats en question dans une revue scientifique prestigieuse et soumise au processus de révision par les pairs. Il faut ensuite patienter au moins deux ans pour laisser le temps à la communauté scientifique de passer les résultats en revue. Si l’explication reçoit l’approbation des autres chercheurs, il faut ensuite s’adresser directement au Clay Mathematics Institute, l’institution qui gère l’attribution des récompenses pour les Prix du Millénaire (https://www.claymath.org/millennium-problems/rules-millennium-prizes).

    Bien cordialement et en vous remerciant de votre lecture,

  18. Il y a un problème avec l’exemple du puzzle car un puzzle peut être vérifié rapidement par un ordinateur en fonction des couleurs alors que notre cerveau lui est influencé par les couleurs, les bruits ect… donc pour moi p/=Np
    Je n’ai pas tout bien compris donc si je raconte n’importe quoi dites le moi

  19. Après si on prend en compte aussi que un algorithmes ne retiens pas des informations mais vérifie juste (sauf si on lui demande je pense) le cerveau lui peux même stocker beaucoup plus de “données” que un ordinateur et que cela du coup peut varier je pense tout simplement que p=np ou p/=np sont tout les deux faux et qu’il n’y a pas de solution viable car le problème concernent aussi tout ce qu’il y a autour de l’ordinateur ou de l’humain (dites moi encore si je dis n’importe quoi)

  20. Et autre question, si p=np, a quoi ça sert d’apprendre et d’étudier ? Théoriquement à rien, à part pour découvrir un problème Np complet qui ne l’étais peut être pas avant

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *