Un mathématicien allemand affirme avoir résolu le problème P=NP

Un million d’euros et une place au Panthéon des mathématiciens : c’est ce qui attend celui qui résoudra l'énigme qui obsède les matheux depuis des décennies.

|
août 25 2017, 8:56am

Quel est le point commun entre le traitement du cancer, le modèle du "capitalisme éthique" et une partie de Super Mario Bros. parfaite ? Il existe une théorie mathématique selon laquelle des problèmes de ce type pourraient être résolus facilement grâce au calcul : il suffirait de mettre au point de meilleurs algorithmes afin de prouver que des problèmes complexes (comme le repliement des protéines, l'efficience des marchés, la combinatoire dans les jeux) ne sont que des variantes de problèmes plus simples et que nous savons déjà résoudre avec les supercalculateurs actuels.

Mais à quoi pourrait ressembler l'algorithme qui rendrait gérables des tâches extrêmement difficiles ? Les problèmes complexes sont-ils fondamentalement différents des problèmes simples ? Est-il possible de réduire les premiers aux seconds afin de les calculer ? Cette question est considérée comme l'une des plus grandes énigmes mathématiques à l'heure actuelle : pour cette raison, elle constitue l'un des sept problèmes mathématiques du prix du millénaire, avec une récompense d'un million de dollars promise à celui ou celle qui y apportera une solution, quelle qu'elle soit.

Voilà qu'un Allemand affirme en avoir une sous la main. Malheureusement, il en tire des conclusions plutôt pessimistes : dans la preuve de 38 pages qu'il a publiée sur arXiv, Norbert Blum, de l'Université de Bonn, conclut que P n'est pas égal à NP. En d'autres termes : les problèmes complexes sont fondamentalement différents des problèmes simples, et nos supercalculateurs ne risquent pas de résoudre nos problèmes les plus complexes de sitôt.

Qu'est-ce que le problème P=NP ?

La conclusion de Blum correspond à l'opinion la plus répandue dans la communauté mathématique, et chez les spécialistes d'informatique théorique. Elle veut que nos ordinateurs et les mathématiques grâce auxquels ils fonctionnent séparent les problèmes en deux catégories : d'une part, les problèmes simples de la classe P, qui peuvent résolus dans un temps « polynomial », c'est-à-dire acceptable ; et d'autre part, les problèmes plus complexes de la classe NP, que nos ordinateurs ne savent pas résoudre rapidement.

Quelques exemples de problèmes NP :

le repliement des protéines : le processus qui confère leur structure aux protéines dans un organisme biologique. Une meilleure compréhension de ce processus pourrait permettre de mieux détecter, voire d'empêcher les erreurs lors de la création des protéines, et donc de soigner certaines formes de cancer.

le problème du représentant de commerce : trouver l'itinéraire optimal pour visiter 15 villes sans repasser deux fois au même endroit ? C'est difficile, même pour un ordinateur. Ce problème appartient à la classe NP.

une partie d'échecs parfaite : il existe beaucoup de coups aux échecs contre lesquels même les ordinateurs les plus puissants ne peuvent calculer de tactique parfaite. De nombreux mathématiciens tiennent cette question pour si complexe qu'elle n'appartiendrait même pas à l'espace NP, mais se situerait au-delà.

Mais tous ces casse-têtes ont un point commun : si leurs solutions sont incroyablement difficiles à trouver, leur validité est très facile à vérifier.

La percée que tout le monde attend : celui qui trouverait la technique parfaite à Super Mario pourrait aussi soigner le cancer.

La division des problèmes en deux classes remonte à une époque antérieure à la naissance de l'informatique grand public. Dans les années 1970, lorsque les ordinateurs faisaient encore la taille d'armoires normandes, il est devenu évident que certains problèmes étaient plus faciles que d'autres à calculer sous forme de code. On a donc réparti ces problèmes en deux classes : les problèmes simples dans la classe P, les problèmes complexes dans la classe NP.

Depuis lors, les mathématiciens ne parviennent pas à s'accorder sur la question de savoir si des algorithmes plus sophistiqués suffiraient à réduire les problèmes NP à des problèmes P, solubles par nos ordinateurs. Si quelqu'un parvenait à prouver qu'un problème NP est en dernière analyse une variante d'un problème P, alors la solution d'un problème NP pourrait alors être la solution de tous les problèmes NP. En clair : celui qui trouverait la technique parfaite à Super Mario pourrait aussi soigner le cancer.

116 mathématiciens courageux se sont déjà essayés à résoudre l'énigme. Jusqu'à présent, aucune de leurs preuves n'a été reconnue comme telle par la communauté des mathématiciens.

Une sorte de « Qui veut gagner des millions ? » pour les mathématiciens

En 2000, le Clay Mathematics Institute (CMI), situé à Cambridge (Massachusetts), a établi une liste de 7 grands problèmes mathématiques non résolus et promis une récompense d'un million de dollars pour chaque solution. C'est comme « Qui veut gagner des millions ? », mais pour les mathématiciens.

Même les experts du domaine considèrent les problèmes du prix du millénaire comme extrêmement difficiles : il faut déjà des connaissances très avancées pour comprendre la formulation des questions. La seule à avoir été résolue jusqu'à présent est la conjecture de Poincaré, grâce au travail de Grigori Perelman. Cependant, le mathématicien russe, au tempérament solitaire, a refusé le prix et la remise de la médaille de Fields destinés à le récompenser.

Si le problème NP=P était effectivement résolu, l'événement n'aurait pas que des conséquences positives, cependant. Au contraire, de nouveaux problèmes surgiraient immédiatement, comme le montre l'exemple du chiffrement des données de cartes bancaires : pour assurer leur protection, les banques partent du principe que même l'ordinateur le plus rapide aurait besoin d'un temps extrêmement long pour décomposer un nombre suffisamment grand en produit de facteurs premiers. Un chiffrement 256-bit tel que celui utilisé par les établissements bancaires pour protéger les paiements par CB est pratiquement impossible à casser, et donc plutôt sûr. Mais si quelqu'un apportait la preuve que P est égal à NP, les banques devraient trouver rapidement une nouvelle méthode de protection. De même, les cryptographes devront revoir les bases même des méthodes de chiffrement pour les échanges d'information sur Internet (le protocole SSL repose sur le principe P≠NP, par exemple).

Que disent les mathématiciens de la preuve de Blum ?

Depuis que l'article de Blum a été publié, les mathématiciens et les informaticiens se cassent la tête pour savoir si le chercheur de Bonn a bien résolu l'un des problèmes du prix du millénaire. Après les premières réactions positives, notamment du mathématicien de Stanford Reza Zadeh, des doutes ont commencé à s'élever sur la validité de la preuve de Blum.

Sur un forum dédié à la théorie mathématique, l'utilisateur Mikhail écrit qu'il a demandé à Alexander Razborov - dont les travaux ont inspiré la preuve de Blum - ce qu'il pensait de l'article préliminaire de Blum. Or, il aurait trouvé une erreur dans l'article : dans l'un des points clés de sa preuve, la fonction Tardos, Blum contredit l'une de ses propres hypothèses, le théorème 6. La preuve de Blum serait donc « nécessairement fausse ». Et le mathématicien Scott Aaronson, qui est une sorte d'autorité sur la question P-NP, a parié 200 000 $ sur son blog que la preuve de Blum serait rejetée.

« Merci de ne plus me poser de questions là-dessus », a écrit Aaronson. « Si à la fin de la semaine l'article n'a pas été réfuté, là vous pourrez revenir vers moi et me traiter d'ignorant et de crétin. »