En résolvant ce problème mathématique, vous pourriez voler tous les bitcoins du monde

Vous avez peut-être entendu parler du fameux problème P = NP. Si vous pouvez prouver ou réfuter son équation énigmatiquement courte, vous gagnerez un million de dollars, voire des milliards de dollars, selon vos scrupules.

L’importance de P = NP réside principalement dans leurs conséquences sur le calcul. Il se trouve que c’est l’un des sept problèmes du Prix du Millénaire, ce qui signifie que le Clay Mathematics Institute de Cambridge, Massachusetts, accordera 1 million de dollars à quiconque parvient à prouver ou réfuter cette affirmation. Mais si vous prouviez que P = NP, vous n’auriez même pas besoin du prix d’un million de dollars. Comme l’a expliqué Scott Aaronson, informaticien théoricien, la semaine dernière, lors d’une conférence dans un auditorium encombré au Los Alamos National Lab au Nouveau-Mexique, prouvant que P = NP ouvrirait des possibilités intrigantes.

“Si quelqu’un prouve P = NP, la première chose à faire est de voler 200 milliards de dollars en Bitcoin. La deuxième chose qu’ils devraient faire, c’est de résoudre tous les autres problèmes liés au Prix du Millénaire”, a dit M. Aaronson.

Pour comprendre cela, il faut savoir que les ordinateurs sont des dispositifs qui résolvent des problèmes, résumés en code lisible par le dispositif informatique physique, sur la base des principes énoncés par Alan Turing. La résolution des problèmes prend un certain nombre d’étapes et un certain temps, le temps nécessaire augmentant à mesure que le problème prend de l’ampleur.

“P” fait référence aux problèmes que les ordinateurs résolvent tout le temps, qu’il s’agisse de quelque chose d’aussi simple que la multiplication de deux chiffres ou de tâches plus complexes comme la navigation sur Internet. Lorsqu’un problème devient de plus en plus complexe, le temps qu’il faut pour le résoudre augmente en “temps polynomial”, où un polynôme est un nombre avec une puissance et un coefficient (comme n²). Si un problème peut être résolu en n² temps et que vous doublez la taille de l’entrée, alors le temps qu’il faudrait pour le résoudre augmenterait de quatre fois.

Pourtant, il y a beaucoup de problèmes où l’on peut déterminer qu’une réponse donnée est correcte dans le temps polynomial, mais qu’il est possible ou non d’arriver à cette réponse dans le temps polynomial. Ces problèmes sont appelés “temps polynomial non déterministe” ou problèmes NP. Le Sudoku est un problème NP difficile à résoudre, facile à vérifier. Un autre exemple important aujourd’hui est la prise en compte de grands nombres dans les nombres premiers. Pour l’instant du moins, il faut beaucoup de temps – plus lent que le temps polynomial – pour factoriser de très grands nombres en nombres premiers, mais vérifier qu’une réponse est correcte est aussi simple que de multiplier les nombres résultants. En effet, cette idée exacte est à la base du cryptage moderne, qui repose sur la génération de clés de sécurité faciles à vérifier mais difficiles à cracker.

De nouvelles preuves mathématiques ont trouvé, et pourraient continuer à trouver, des solutions P à certains de ces problèmes de NP. Le problème P = NP demande si chaque problème NP a une solution P, ou s’il existe un problème NP qui ne peut absolument pas être résolu dans P. Il semble qu’il devrait être évident que P n’est pas égal NP, mais il n’est pas rigoureusement prouvé par des calculs mathématiques. Et s’il vous arrive de prouver que P est égal à NP, vous aurez également démontré qu’il existe des algorithmes de temps polynomial pour un grand nombre de problèmes informatiques très importants. Vous pourriez vous rendre très riche. Les clés de sécurité et d’exploitation de bitcoins reposent sur des problèmes NP difficiles à résoudre et à contrôler.

Les ordinateurs quantiques, qui sont basés sur des mathématiques différentes des ordinateurs classiques, ne promettent pas de solutions P à tous les problèmes des NP. On pensait autrefois qu’ils pourraient être en mesure de résoudre la classe la plus difficile de problèmes NP, appelés problèmes NP-complets. Si vous pouviez trouver une solution efficace à ces problèmes, vous seriez en mesure de trouver des solutions efficaces à tous les problèmes des NP. Cela inclut le problème du voyageur de commerce et une foule d’autres problèmes d’optimisation similaires. Mais les ordinateurs quantiques n’ont pas été à la hauteur de ce battage médiatique. Au lieu de cela, les ordinateurs quantiques pourraient résoudre certains problèmes de P en un temps plus court (comme dans un polynôme inférieur) ou déplacer certains problèmes de NP dans la généralisation quantique de P, appelée BQP ou “Bounded-Error Quantum Polynomial Time”.

Alors, allez-y et essayez de prouver que P est ou n’est pas égal à NP. Si vous réussissez, vous gagnerez au moins un million de dollars, et peut-être beaucoup, beaucoup plus. Si vous n’y arrivez pas, eh bien, j’espère que vous aurez mené une vie significative en faisant des recherches sur la théorie computationnelle.

Lire aussi : Voici le top 10 des technologies émergentes de 2019

Source : Gizmodo – Traduit par Anguille sous roche