Gagner un million de dollars en résolvant un problème de math !

Après une explosion de son cours en 2017 (avec une valeur maximale à plus de 16 000 dollars), le Bitcoin aura finalement vu le soufflé retombé l’année suivante. Mais après une lente remontée, la crypto-monnaie la plus célèbre du monde stagne aux alentours de la barre des 10 000 dollars, pour le plus grand bonheur de ses possesseurs. Seulement, un problème mathématique pourrait bien tirer un trait sur l’Histoire du Bitcoin, le problème P = NP.

L’UN DES SEPT PROBLÈMES DU PRIX DU MILLÉNAIRE

Le problème P = NP est considéré comme l’un des problèmes mathématiques les plus ardus du moment. Membre éminent des problèmes du prix du millénaire de l’Institut de mathématiques Clay, sa résolution permet d’empocher la modique somme d’un million de dollars, et plus globalement de révolutionner les méthodes de calcul des ordinateurs. 

Représentation visuelle des deux configurations possibles.

En informatique théorique, la complexité d’un problème peut être grossièrement divisée en deux catégories : P ou NP (pour ‘non déterministe polynomial’). Si un problème est classé dans la catégorie P, c’est qu’il est considéré comme réalisable dans un délai très court. Si le problème est classé NP, c’est que le temps nécessaire à sa résolution est très élevé. Et comme l’a expliqué Scott Aaronson, dont le domaine de prédilection est l’informatique théorique, durant une conférence au Laboratoire national de Los Alamos dans le Nouveau-Mexique, prouver que P=NP, le résultat serait intéressant : 

« Si quelqu’un prouve que P=NP, la première chose qu’il devrait faire c’est de voler 200 millions de dollars en Bitcoin. La seconde chose qu’il devrait faire c’est de résoudre les autres problèmes du prix du millénaire. »

La question que pose le problème P=NP est simple : ‘tous les problèmes NP ont-ils des solutions P ?‘.Si ce problème est un jour complété, résoudre un Sudoku ne prendrait que quelques secondes pour un ordinateur. Le minage du Bitcoin serait alors grandement facilité et un mineur pourrait s’enrichir extrêmement rapidement. Seulement, vous vous en doutez, si la solution était publiée, le cours du Bitcoin s’effondrerait. Même si certains problèmes peuvent profiter d’une solution classée comme P, de nombreux problèmes restent NP.

Néanmoins, certains problèmes longs et difficiles à résoudre peuvent, un jour, être résolu par un algorithme précis, leur permettant de changer de classe. Si le problème P=NP est un jour résolu, les domaines de la cryptologie, de l’informatique, des mathématiques, de l’ingénierie ou encore de l’économie en seront chamboulés. Un jour qui pourrait bien ne jamais arriver, malgré les brillants esprits qui peuplent cette planète.