Blog personnel d'Arthur Milchior

-Déjà, il faut savoir deux choses: d'une part, il vaut un million de dollars^[1]. Il a été déclaré comme un des 7 plus grands problèmes mathématiques du millénaire. Et en plus, il est relativement simple à comprendre, ce qui le rend d'autant plus énervant.

Je vais te donner un exemple: Tu sais ce que c'est que la division ? Par exemple, si je te demande quels nombres divisent 12, tu me réponds ?
-2, 3, 6... 4... Ah, et 12 et 1.
-C'était pas très compliqués. Maintenant, si je te donne un nombre qui fait un petit milliers de chiffres, tu fais comment pour trouver des diviseurs ?
-Je sais pas... je les testes un par un. Je teste que les impairs.
-Non, tester tous les nombres, ça prend trop de temps. Même sur les ordinateurs super rapide, c'est pas faisable, pas pour un nombre qui fait des milliers de chiffres. Faut que tu réalises que un millier de chiffres, ça fait un milliard de milliard de milliards... et ça 100 fois, de nombres à tester.

Eh bien en fait, on ne sait pas. Oh en vrai, on a bien quelques astuces pour aller un peu plus vite, mais personne ne sait le faire rapidement. Et ce qui est plus énervant encore, c'est qu'on ne sait pas si c'est mathématiquement impossible. Ou si c'est juste que pour l'instant, on est trop bête pour avoir trouvé la manière de le faire. Et bien, le problème du millénaire, c'est ça, en gros. Soit trouver un moyen de résoudre ce problème, mais on pense pas que ça soit faisable, soit prouver mathématiquement que c'est impossible. P, c'est ce que tu peux faire rapidement, pour une définition formelle de «rapide». Et NP c'est ce que tu peux vérifier rapidement. Parce que, si je te demande les diviseurs de 221, ça peut te prendre du temps, mais si je te dis que 13 le divise, tu peux le vérifier rapidement, 221 divisé par 13, ça fait 17. Et on se demande s'il y a des choses qu'on peut vérifier, mais qu'on peut montrer qu'on ne pourra pas trouver rapidement.
-Tu peux pas prouver qu'on peut pas faire quelque chose. Y a toujours des moyens de faire des trucs auxquels on a pas pensé. Sinon, il y a cent ans, on aurait pu prouver qu'on ne peut pas aller sur la lune.
-En fait si. C'est l'avantage des mathématiques, l'ordinateur, on sait exactement ce que c'est. Donc il y a des trucs qu'on a démontré qu'on ne pourra jamais faire. Par exemple répondre à tous les problèmes mathématiques, et là c'est pas une question de temps, il y en a qui n'ont juste pas de réponse^[2], on ne sait même pas lesquels, et le pire, c'est que l'immense majorité des problèmes n'ont pas de réponses^[3]. Mais là, avec la recherche des diviseurs, on est dans l'inconnu, on pense qu'on pourra jamais faire, mais on sait pas comment le prouver.
-«Ils ont réussis parce qu'ils ne savaient pas que c'est impossible.»
-Bien sûr, si tu veux être exacte, on peut juste dire «c'est impossible pour les ordinateurs actuels». Ou même les ordinateurs futurs qui se contentent juste d'aller plus vites. Parce là, pour un gros nombre, ton calcul qui va te prendre des milliards de milliards d'années, même si ton ordinateur va mille fois plus vite, t'auras toujours des millions de milliards d'années à attendre... Mais on ne peut pas prouver mathématiquement qu'un jour la Pythie de Delphes ne vas pas arriver et nous donner des réponses à nos questions compliqués. Le pire, c'est que je ne rigole pas, il y a des branches des mathématiques qui étudient ce qu'on pourrait faire si on avait des oracles. Mais plus sérieusement, y a d'autres sortes d'ordinateurs imaginés - les ordinateurs quantiques
-Comme le chat de Schrödinger.
-C'est pas faux. D'autant qu'on ne sait pas si on pourra en réaliser un jour en vrai, ça semble compliquer. En théorie, ils pourraient répondre super rapidement à ce genre de question. Ils pourront pas être utilisé pour word, juste pour des calculs théoriques compliqué, comme trouver des diviseurs. Le souci, c'est que pour l'instant, le plus grand nombre dont les diviseurs ont été trouvés, c'est 21... pas super efficace.
-De toute façon, ça sert à rien. Pourquoi vous y passé autant de temps ?
-En fait non. Le pire, c'est que ce problème là est super important. Si tu trouves comment avoir les diviseurs rapidement, en vrai, c'est largement plus d'un million que ça vaut. Parce que, pour des raisons trop complexe à expliquer, une énorme partie de la sécurité informatique repose sur l'idée qu'on ne sait pas trouver rapidement des diviseurs. Ou qu'on ne sait pas trouver certains trucs. Si tu sais le faire, alors, y a plus de communication secrètes, donc plus de payement en ligne, puisque tout le monde pourrait lire ton mot de passe sur internet, plus de carte bleue à puce... En tout cas, pas de manière aussi simple. L'avantage, c'est que il y a des problèmes qui ressemblent, qu'on sait «vérifier» comme j'avais expliqué, donc qui sont dans NP, qu'on saurait alors peut-être résoudre. Des problèmes de physique, de biologie, de mathématiques, etc... donc y a des optimistes qui espèrent P=NP, ça permettrait de faire d'immense progrès scientifiques, dans des tas de domaines différents en plus, vu que l'ordinateur est utilisé partout !
-Et donc toi, tu travailles sur ça ?
-Ah non. Ça, c'est un des 7 plus gros problèmes mathématiques du millénaire. J'ai aucune chance de résoudre ça. Je fais des trucs, on va dire, similaire de loin, mais avec des modèles BEAUCOUP plus simples. Sur lesquels je suis capable de montrer que des trucs sont impossibles. Ce qu'on se dit, en mathématiques, c'est qu'en empilant des tas et des tas de résultats, petits à petits, on comprendra mieux tout ça, et on finira par voir comment faire ces preuves. On est des nains juchés sur des épaules de géants. Bon, en fait, on fait une pyramide de nains sur des épaules de géants, et on suppose qu'à la longue, on sera assez haut pour avoir des réponses. Mais, souvent, en mathématiques, on ne sait pas qui va trouver le bon chemin, donc on explore le labyrinthe au hasard, et je mélange les métaphores. Mais en tout cas, je te jure, c'est passionnant de traîner là, tenter d'évoluer, de comprendre, et de découvrir des trucs neufs. Même si, je suis juste pas sûr d'avoir la réponse à P=NP de mon vivant, ce qui est dommage, car j'aimerai bien savoir.