Le problème vieux de 50 ans qui échappe à l'informatique théorique

Une solution à P vs NP pourrait débloquer d'innombrables problèmes de calcul ou les garder à jamais hors de portée.

Le problème de l'arbre de Steiner : Connectez un ensemble de points avec des segments de ligne de longueur totale minimale. Derek Brahney

par

• Siobhan Roberts page d'archives

27 octobre 2021

un. Le lundi 19 juillet 2021, au milieu d'un autre étrange été pandémique, un informaticien de premier plan dans le domaine de la théorie de la complexité a tweeté un message de service public sur un snafu administratif dans un journal. Il a signé avec un très chargé

Joyeux lundi.

Cette histoire faisait partie de notre numéro de novembre 2021

• Voir la suite du problème
• S'abonner

Dans un univers parallèle, cela aurait pu être un lundi très heureux. Une preuve était apparue en ligne dans la prestigieuse revue ACM Transactions on Computational Theory, qui fait le commerce de recherches originales exceptionnelles explorant les limites du calcul réalisable. Le résultat prétendait résoudre le problème de tous les problèmes - le Saint Graal de l'informatique théorique, d'une valeur d'un million de dollars et d'une renommée rivalisant à jamais avec celle d'Aristote.

Ce problème précieux - connu sous le nom de P versus NP - est considéré à la fois comme le plus important en informatique théorique et en mathématiques et complètement hors de portée. Il aborde des questions centrales sur la promesse, les limites et les ambitions du calcul, en demandant :

Pourquoi certains problèmes sont-ils plus difficiles que d'autres ?

Quels problèmes les ordinateurs peuvent-ils résoudre de manière réaliste ?

Combien de temps cela prendra?

Et c'est une quête avec de gros gains philosophiques et pratiques.

Écoutez, cette question P contre NP, que puis-je dire ? Scott Aaronson, informaticien à l'Université du Texas à Austin, a écrit dans son mémoire d'idées , L'informatique quantique depuis Démocrite . Les gens aiment le décrire comme 'probablement le problème central non résolu de l'informatique théorique'. C'est un euphémisme comique. P vs NP est l'une des questions les plus profondes que les êtres humains se soient jamais posées.

Une façon de penser aux protagonistes de cette histoire est la suivante :

P représente les problèmes qu'un ordinateur peut facilement résoudre.

NP représente des problèmes qui, une fois résolus, sont faciles à vérifier, comme les puzzles ou le Sudoku. De nombreux problèmes de NP correspondent à certains des problèmes les plus tenaces et les plus urgents auxquels la société est confrontée.

La question à un million de dollars posée par P contre NP est la suivante : ces deux classes de problèmes sont-elles identiques ? C'est-à-dire que les problèmes qui semblent si difficiles pourraient en fait être résolus avec un algorithme dans un délai raisonnable, si seulement le bon algorithme diaboliquement rapide pouvait être trouvé ? Si tel est le cas, de nombreux problèmes difficiles peuvent soudainement être résolus. Et leurs solutions algorithmiques pourraient entraîner des changements sociétaux aux proportions utopiques - en médecine et en ingénierie et en économie, en biologie et en écologie, en neurosciences et en sciences sociales, dans l'industrie, les arts, même la politique et au-delà.

Parfois, les classifications évoluent - les problèmes difficiles se révèlent faciles lorsque les chercheurs trouvent des solutions plus efficaces. Tester si un nombre est premier, par exemple, est connu pour être dans la classe NP depuis le milieu des années 1970. Mais en 2002, trois informaticiens de l'Indian Institute of Technology Kanpur ont conçu une preuve inconditionnelle et un algorithme intelligent qui a finalement confirmé que le problème était également dans P.

Si tout les problèmes délicats pourraient être transformés avec un tel tour de passe-passe algorithmique, les conséquences pour la société – pour l'humanité et notre planète – seraient énormes.

Pour commencer, les systèmes de cryptage, dont la plupart sont basés sur des problèmes NP, seraient piratés. Nous aurions besoin de trouver une approche complètement différente pour envoyer des communications sécurisées. Le repliement des protéines, un grand défi en biologie vieux de 50 ans, deviendrait plus facile à résoudre, débloquant de nouvelles capacités pour concevoir des médicaments qui guérissent ou traitent les maladies et découvrir des enzymes qui décomposent les déchets industriels. Cela signifierait également trouver des solutions optimales aux problèmes difficiles de tous les jours, comme planifier un voyage en voiture pour atteindre toutes les destinations avec un minimum de conduite, ou asseoir les invités au mariage afin que seuls les amis partagent la même table.

Depuis la création du problème P contre NP il y a 50 ans - émergeant de l'intersection capitale de la logique mathématique et de la technologie informatique électronique - les chercheurs du monde entier ont fait des tentatives herculéennes pour trouver une solution. Certains informaticiens ont suggéré que les efforts pourraient être mieux comparés à ceux de Sisyphe, qui a travaillé sans résolution. Mais alors que ceux qui ont exploré le problème en premier manquent de temps pour trouver une solution, les nouvelles générations se lancent avec joie dans la quête.

Pour Manuel Sabin, un informaticien qui vient de terminer un doctorat à l'UC Berkeley, l'attrait consiste à sonder l'impossibilité de problèmes dont vous ne connaîtrez pas la réponse tant que le soleil n'aura pas englouti la terre. La recherche pourrait être chimérique, mais Sabin regretterait de ne pas s'être penché sur ces moulins à vent.

Timothy Gowers, mathématicien à l'Université de Cambridge, l'appelle l'une de mes maladies mathématiques personnelles. Il a perdu l'été 2013 à la poursuite, après avoir demandé aux étudiants un essai sur le sujet lors d'un test. Comme il l'a raconté sur son blog : Après avoir noté les essais en juin, j'ai pensé que je passerais une heure ou deux à réfléchir à nouveau au problème, et cette heure ou deux s'est accidentellement transformée en environ trois mois.

Le problème du voyageur de commerce : trouver l'itinéraire le plus court possible qui visite chaque ville une fois, pour finalement revenir à la ville d'origine.

DEREK BRAHNEY

La quête a même déconcerté l'informaticien de l'Université de Toronto, Stephen Cook, qui a défini le problème et lancé le domaine de la complexité computationnelle avec un article fondateur en 1971. Pour ce travail, il a remporté le prix Turing, l'équivalent informatique du prix Nobel. Mais il n'a pas eu de chance de trouver une solution. Cook dit qu'il n'a jamais eu de bonnes idées - c'est tout simplement trop difficile.

deux. Michael Sipser, un informaticien du MIT, estime qu'il a passé, au total, jusqu'à une décennie sur le problème. Il s'est intéressé pendant ses études supérieures dans les années 1970 et il a parié une once d'or avec son camarade Len Adleman que le problème serait résolu d'ici la fin du siècle (Sipser a payé).

Dans les années 1980, il a obtenu un beau résultat en résolvant une version du problème avec un modèle de calcul restreint, ce qui a conduit à une période passionnante sur le terrain avec plusieurs beaux résultats, laissant espérer qu'une solution pourrait ne pas être trop éloignée.

Sipser revient toujours sur le problème de temps en temps, et il est un ambassadeur inébranlable, livrant d'innombrables conférences sur le sujet.

La façon dont il entre dans une explication accessible de P contre NP est avec un problème de multiplication de base : 7 × 13 = ?

La réponse, 91, est assez facile à calculer dans votre tête. Bien que multiplier des nombres plus grands ne soit pas aussi facile, cela ne prendrait pratiquement pas de temps à un ordinateur.

Mais renverser ces problèmes est une autre affaire. Considérons, par exemple, trouver les deux nombres premiers à 97 chiffres qui se multiplient pour produire ce très grand nombre :

0437213507 5003588856 7418240490 0228427275 7930037346 310 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609

Ce problème de factorisation faisait partie d'un challenge évaluant la difficulté de cracker les clés RSA utilisées en cryptographie. Pour le résoudre, il a fallu cinq mois de calcul continu à 80 processeurs, explique Sipser, ce qui équivaut à environ 33 ans avec un seul processeur. La factorisation est un problème difficile car toutes les méthodes actuelles cherchent la réponse par la force brute, en vérifiant une par une le nombre astronomique de possibilités. Même pour un ordinateur, c'est un processus lent.

La question intéressante ici est, avez-vous vraiment besoin de chercher? dit Sipser. Ou existe-t-il un moyen de résoudre le problème de factorisation qui zoome rapidement sur la réponse sans chercher ? Nous ne connaissons pas la réponse à cette question.

Des questions comme celle-ci sont au cœur de la complexité informatique, un domaine plein de problèmes bestiaux que les chercheurs tentent de comprendre. Aaronson a assemblé un Complexity Zoo, un catalogue en ligne avec 545 classes de problèmes (et plus encore). Chacun est classé selon sa complexité, ou sa difficulté, et les ressources – temps, mémoire, énergie – nécessaires pour trouver des solutions. P et NP sont les principales attractions.

Comme le voulait la sérendipité scientifique, un mathématicien soviétique, Leonid Levin, a convergé vers un résultat équivalent à celui de Cook à peu près au même moment.

P est la classe qui a tout commencé. C'est la classe des problèmes qui peuvent être résolus par un ordinateur en un temps raisonnable. Plus précisément, les problèmes P sont ceux pour lesquels le temps nécessaire pour trouver une solution peut être décrit par une fonction polynomiale, telle que n ^ 2. Dans les algorithmes en temps polynomial, n est la taille de l'intrant, et la croissance par rapport à cet intrant se produit à un taux raisonnable (dans ce cas, à la puissance deux).

En revanche, certains problèmes NP difficiles ne peuvent être résolus que par des algorithmes avec des temps d'exécution définis par une fonction exponentielle, telle que 2 ^ n - produisant un taux de croissance exponentiel (comme avec la propagation de covid). NP, comme le décrit Aaronson, est la classe des espoirs déçus et des rêves vains. Il est cependant prompt à clarifier une idée fausse courante : tous les problèmes NP ne sont pas difficiles. La classe NP contient en fait la classe P — parce que les problèmes avec des solutions faciles sont, bien sûr, aussi faciles à vérifier.

Les problèmes les plus difficiles de NP ont souvent des applications pratiques capitales. Pour ces problèmes, une recherche exhaustive par force brute d'une solution se poursuivrait probablement pendant une durée irréaliste - le temps géologique - avant de produire une réponse. Si un algorithme de recherche par force brute est le meilleur algorithme possible, alors P n'est pas égal à NP.

Et chez les connaisseurs, c'est apparemment le consensus, que certains assimilent davantage à la croyance religieuse : P ≠ NP. La plupart n'autorisent qu'une lueur d'espoir que le contraire se révélera vrai. Je lui donnerais 2 à 3% de chances que P soit égal à NP, dit Aaronson. Ce sont les cotes de paris que je prendrais.

Le résultat publié en juillet a présenté une preuve exacte de ce long shot. Mais ce n'était que la dernière d'une longue tradition de preuves qui ne réussissent pas. Moins d'un jour après sa publication, dans une tournure digne des Monty Python, l'article a été retiré du journal en ligne ; puis il a semblé réapparaître brièvement avant de disparaître définitivement. Il s'agissait de la version la plus récente d'un article que l'auteur avait publié plus de 60 fois sur le serveur de préimpression arXiv au cours de la dernière décennie. Le rédacteur en chef du journal a expliqué sur Twitter que le résultat avait été rejeté, mais dans un cas d'erreur humaine, la disposition du journal avait en quelque sorte changé de rejeter à accepter et la preuve avait trouvé son chemin vers la publication.

3. Début août, lorsque j'ai rencontré Steve Cook dans son bureau sur le campus, il n'avait ni vu ni entendu parler de ce dernier snafu de preuve P contre NP. Aujourd'hui âgé de 81 ans, il n'avait pris sa retraite que récemment, car sa mémoire faisait défaut. C'est pourquoi nous avons James ici, a-t-il dit - son fils James, 36 ans, également informaticien, s'était joint à nous pour ma visite. Steve était en train de vider son bureau. Un bac de recyclage géant se dressait au milieu de la pièce, rempli de vieux numéros jaunis du Journal of Symbolic Logic, une pile d'annuaires téléphoniques torontois surdimensionnés attendant à proximité.

Au fil des ans, Cook a vu de nombreuses preuves prétendant résoudre le problème P vs NP. En 2000, après que le Clay Mathematics Institute l'ait nommé l'un des sept problèmes du millénaire non résolus (chacun valant un prix d'un million de dollars), il a été inondé de messages de personnes qui pensaient avoir triomphé. Tous les résultats étaient faux, sinon carrément faux. Environ la moitié a affirmé avoir prouvé que P est égal à NP ; l'autre moitié est allée dans la direction opposée. Il n'y a pas si longtemps, une personne a affirmé avoir prouvé les deux.

Cook, dans son article de 1971, a supposé que P n'est pas égal à NP (il l'a formulé en utilisant une terminologie différente courante à l'époque). Depuis, il a investi beaucoup de temps, bien qu'indéterminé, pour établir que c'est le cas. Je n'ai pas un bon souvenir d'avoir travaillé dur, dit-il, mais ses collègues se souviennent que chaque fois qu'ils se rendaient au département le week-end, Steve était là dans son bureau.

À moins qu'il ne soit en course de voiliers, Cook n'est pas du genre à se précipiter ; il aime donner du temps à une idée. Et ses anciens élèves se souviennent d'un manque flagrant de fanfaronnade. L'informaticienne Anna Lubiw, de l'Université de Waterloo, dit que lorsqu'il a enseigné le théorème de Cook - qui fait partie de cet article pionnier - il ne l'a jamais mentionné comme tel et n'a même jamais laissé entendre qu'il était la personne qui l'avait prouvé. Maria Klawe, mathématicienne et informaticienne et présidente du Harvey Mudd College, dit qu'elle corrigeait régulièrement Cook lorsqu'il s'égarait en enseignant des preuves qu'il connaissait par cœur : il restait coincé et disait : 'D'accord'. Dites-moi comment se passe la preuve. » Cook était également connu pour sa modestie dans les demandes de subvention et les rapports relatifs à ses recherches – il confesserait : Honnêtement, j'ai fait peu de progrès…

Histoire connexe

L'évolution de l'informatique Le calcul des niveaux d'énergie d'un atome d'hélium en 1958 était beaucoup plus difficile qu'il ne l'est aujourd'hui. Mais une comparaison des méthodes d'hier et d'aujourd'hui révèle certaines anomalies contre-intuitives concernant l'impact de l'informatique.

Il a cependant fait des progrès en recrutant James pour défendre la cause. Très tôt, James a manifesté un intérêt pour les mathématiques et l'informatique - à neuf ans, il a exhorté son père à lui enseigner l'algèbre booléenne et la logique. Il y a quelques années, après avoir obtenu un doctorat à Berkeley et fait un passage chez Google, il s'est lancé en tant que chercheur indépendant se concentrant sur divers projets, certains d'entre eux indirectement liés à P vs NP. Et malgré le palmarès, James, qui ressemble étrangement à son père, n'a pas peur d'avoir hérité d'une quête apparemment interminable. Il le considère comme n'importe quel effort mathématique : c'est un casse-tête amusant. Il doit y avoir une réponse à ces questions, dit-il. Et c'est comme, allez, quelqu'un doit le résoudre. Comprenons cela. Ça fait longtemps. C'est embarrassant que nous ne connaissions pas encore la réponse.

Le manque de progrès n'a pas empêché cette communauté de joyeux Sisyphes de célébrer le 50e anniversaire de la complexité computationnelle. Les festivités ont commencé en 2019, lorsque des passionnés du monde entier se sont réunis au Fields Institute for Research in Mathematical Sciences, à l'Université de Toronto, pour un symposium en l'honneur de Cook. Christos Papadimitriou, informaticien à l'Université de Columbia qui a passé une grande partie de sa carrière à travailler sur P vs. NP, a ouvert l'événement par une conférence publique, revenant non pas sur un demi-siècle mais sur des millénaires.

Il a commencé par décrire des quêtes séculaires de solutions - utilisant des outils algébriques ou la règle et le compas, qu'il considérait comme des formes rudimentaires de calcul. L'histoire de Papadimitriou est finalement arrivée à Alan Turing, le mathématicien britannique dont l'article de 1936 sur les nombres calculables a formalisé les notions d'algorithme et de calcul. Turing a également montré - avec son idée d'une machine informatique universelle - qu'il n'y a pas de moyen mécanique (c'est-à-dire exécuté par une machine) pour prouver la vérité ou la fausseté des énoncés mathématiques; aucun moyen systématique de distinguer le prouvable de l'improuvable.

Papadimitriou a déclaré qu'il considérait l'article de Turing comme l'acte de naissance de l'informatique - et l'acte de naissance dit que l'informatique est née avec une compréhension stricte de ses propres limites. Il a estimé que l'informatique est le seul domaine connu du discours scientifique né avec une telle conscience, contrairement aux autres sciences, qui comprennent leurs propres limites, comme le reste d'entre nous, à la fin de l'âge mûr.

Peu de temps après que les idées de Turing (et des idées similaires d'autres) se soient concrétisées dans les premiers ordinateurs, les scientifiques ont été confrontés à des questions sur les capacités et les limites inhérentes aux machines. Au début des années 1950, John von Neumann, le pionnier américano-hongrois de l'ordinateur moderne, s'est vanté d'un algorithme selon lequel il était polynomial, comparé au titulaire exponentiel, comme l'a rappelé Papadimitriou - il avait déjoué un algorithme lent par un rapide. C'était l'aube d'une nouvelle théorie : la théorie de la complexité computationnelle. L'essentiel était que seuls les algorithmes polynomiaux sont en quelque sorte bons ou pratiques ou valent la peine de viser un problème, alors qu'un algorithme exponentiel, a déclaré Papadimitriou, est l'équivalent algorithmique de la mort.

Cook a commencé à penser à la complexité au milieu des années 1960. Alors qu'il travaillait sur son doctorat à Harvard, il s'est demandé s'il était possible de prouver, compte tenu de certains modèles de calcul, que la multiplication est plus difficile que l'addition (cela reste un problème ouvert).

En 1967, selon un livre sur Cook à paraître de l'Association for Computing Machinery (ACM), alors qu'il était postdoctoral à Berkeley, il a rédigé des notes de cours qui contenaient la graine de son grand résultat. Il avait élaboré une formulation des classes de complexité connues sous le nom de P et NP, et il a posé la question de savoir si P était égal à NP. (À peu près au même moment, d'autres, dont l'informaticien Jack Edmonds, maintenant retraité de l'Université de Waterloo, tournaient autour des mêmes idées.)

Mais le domaine de l'informatique ne faisait que commencer, et pour la plupart des scientifiques et des mathématiciens, de telles idées étaient inconnues, voire carrément étranges. Après quatre ans au département de mathématiques de Berkeley, Cook a été considéré pour la permanence mais n'a pas offert de poste. Il avait des avocats dans le nouveau département d'informatique de l'université, et ils ont fait pression pour qu'il obtienne un poste dans leurs rangs, mais le doyen n'était pas enclin à donner un poste à quelqu'un que les illustres mathématiciens avaient refusé.

La plupart des théoriciens de la complexité rêvent un peu plus petit, optant plutôt pour des approches indirectes.

En 1970, Cook a déménagé à l'Université de Toronto. L'année suivante, il publie sa percée. Soumis à un symposium de l'ACM qui s'est tenu en mai à Shaker Heights, Ohio, l'article a affiné le concept de complexité et défini une manière de caractériser les problèmes les plus difficiles de NP. Il s'est avéré, dans un éclair d'alchimie algorithmique, qu'un problème, connu sous le nom de problème de satisfiabilité (recherche d'une solution pour une formule étant donné un ensemble de contraintes), était en quelque sorte le problème le plus difficile de NP, et que tous les autres problèmes de NP pourrait y être réduit.

C'était un théorème crucial : s'il existe un algorithme en temps polynomial qui résout le problème de satisfaisabilité, alors cet algorithme servira de clé squelette, déverrouillant des solutions à tous les problèmes de NP. Et s'il existe une solution en temps polynomial pour tous les problèmes de NP, alors P = NP.

Parmi les informaticiens, le théorème de Cook est emblématique. Leslie Valiant, de Harvard, a rappelé lors du symposium de 2019 précisément où et quand il en avait entendu parler pour la première fois. Après avoir terminé des études de premier cycle en mathématiques, il avait commencé un doctorat en informatique. Bien qu'il y ait eu des cours et des diplômes dans ce domaine naissant, a-t-il dit, il semblait éphémère, manquant peut-être d'un contenu intellectuel profond. C'était une grave inquiétude pour les gens qui faisaient de l'informatique à l'époque, a-t-il dit. Ils ont demandé : « Est-ce un champ ? Où va-t-il ?’ Un jour, Valiant tomba sur le journal de Cook. Il l'a lu du jour au lendemain. J'étais transformé, dit-il. En un instant, mes préoccupations concernant l'informatique ont été très réduites. Ce papier - pour moi, il a vraiment fait le champ. Je pense que cela a fait de l'informatique – en a fait quelque chose de substantiel.

Et puis, comme le raconte l'histoire, après le théorème de Cook, il y a eu un déluge.

En 1972, Dick Karp, un informaticien à Berkeley, après avoir lu l'article ésotérique de Cook, a démontré que bon nombre des problèmes informatiques classiques avec lesquels il était intimement familiarisé - essentiellement tous les problèmes qu'il ne savait pas résoudre, tirés de la programmation mathématique, la recherche opérationnelle, la théorie des graphes, la combinatoire et la logique computationnelle possédaient la même propriété transformationnelle que Cook avait trouvée avec le problème de satisfaisabilité. Au total, Karp a trouvé 21 problèmes, dont le problème du sac à dos (recherche de la manière optimale d'emballer un espace restreint avec les objets les plus précieux), le problème du voyageur de commerce (trouver l'itinéraire le plus court possible qui visite chaque ville une fois et revient à la ville d'origine), et le problème de l'arbre de Steiner (cherchant à connecter de manière optimale un ensemble de points avec des segments de droite de longueur totale minimale).

Karp a montré que cet ensemble spécial de problèmes était tous équivalents, ce qui a démontré à son tour que le modèle identifié par Cook n'était pas un phénomène isolé, mais plutôt une méthodologie de classification d'une puissance et d'une portée surprenantes. C'était une sorte de test décisif, identifiant la classe de ce qui est devenu connu sous le nom de problèmes NP-complets : une solution à n'importe lequel les résoudrait tous.

Papadimitriou considère la NP-complétude comme un outil polyvalent. Si vous ne pouvez pas résoudre un problème, essayez de prouver qu'il est NP-complet, car cela vous fera peut-être gagner beaucoup de temps, a-t-il déclaré lors de la conférence publique - vous pouvez abandonner une solution exacte et passer à la résolution d'une approximation ou variation du problème à la place.

Dans le grand balayage de l'histoire, Papadimitriou voit le phénomène de NP-complétude et la quête P contre NP comme le destin de l'informatique. Car, comme le voulait la sérendipité scientifique, un mathématicien soviétique, Leonid Levin, a convergé vers un résultat équivalent à celui de Cook à peu près au même moment. Levin, maintenant à l'Université de Boston, a fait son travail derrière le rideau de fer. Après avoir reçu une plus grande attention (il a immigré en Amérique en 1978), le résultat est devenu connu sous le nom de théorème de Cook-Levin.

Et dans une autre coda une dizaine d'années plus tard, une lettre perdue a été découverte dans les archives de Princeton du logicien autrichien Kurt Gödel. En 1956, il avait écrit à von Neumann pour lui demander si un problème de logique - qui dans le langage moderne serait appelé NP-complet - pouvait être résolu en temps polynomial. Il a estimé que cela aurait des conséquences de la plus grande ampleur.

Le problème des cliques : recherchez des cliques dans un graphique, comme un certain sous-ensemble d'amis dans un réseau social.

DEREK BRAHNEY

Quatre. Bien qu'un demi-siècle de travail n'ait rien donné de proche d'une solution, certains résultats captivent au moins l'imagination : un article de 2004 a revendiqué une preuve pour P = NP en utilisant des bulles de savon comme mécanisme de calcul analogique (film de savon, naturellement l'alignement dans la configuration d'énergie minimale, résout d'une certaine manière le problème de l'arbre de Steiner NP-complet).

De nos jours, c'est un oiseau rare d'un informaticien - par exemple, Ron Fagin, un boursier d'IBM - qui s'attaque au problème de front. Dans les années 1970, il a produit le théorème de Fagin, qui caractérisait la classe NP en termes de logique mathématique. Et il a résolu le problème plus d'une fois, mais les résultats n'ont jamais duré plus de quelques jours avant qu'il ne trouve un bogue. Fagin a récemment obtenu un financement pour un projet P contre NP du programme Exploratory Challenges d'IBM soutenant la recherche aventureuse. Pour expliquer pourquoi il s'y tient, il aime citer Theodore Roosevelt, qui disait qu'il vaut bien mieux oser de grandes choses que de se ranger parmi ceux qui vivent dans un crépuscule gris qui ne connaît ni victoire ni défaite.

Mais la plupart des théoriciens de la complexité rêvent un peu plus petit, optant plutôt pour des approches indirectes - incliner le problème, le remodeler ou le recadrer, explorer les environs connexes et réduire davantage l'arsenal d'outils qui pourraient être déployés contre lui (beaucoup sont maintenant connus pour être inutiles ).

Ryan Williams, informaticien au MIT, tente d'éclairer le problème à la fois d'en haut et d'en bas, en étudiant la nature des limites supérieures et des limites inférieures des problèmes de calcul de base. Une limite supérieure, en termes simples, est une affirmation mathématique spécifique selon laquelle il existe un algorithme concret qui résout un problème particulier sans dépasser une certaine quantité de ressources (temps, mémoire, énergie). Une limite inférieure est l'opposé intangible : c'est une affirmation générale d'impossibilité, montrant qu'aucun algorithme de ce type n'existe universellement. L'un des objectifs de la recherche de Williams est de rendre les bornes inférieures constructives et concrètes - des objets mathématiques dotés de caractéristiques descriptibles. Il pense que des approches plus constructives des bornes inférieures sont précisément ce qui nous manque dans les approches actuelles de la théorie de la complexité.

Williams a fixé la probabilité que P ≠ NP à un niveau assez modéré de 80 %. Mais dernièrement, certains chercheurs dans le domaine expriment des doutes même sur ce niveau de certitude. De plus en plus, je commence à me demander si P est égal à NP, déclare Toniann Pitassi, informaticien à l'Université de Toronto et ancien étudiant au doctorat de Cook. Son approche pour contourner le problème consiste à étudier à la fois des analogues à grande échelle et à échelle réduite, des modèles plus difficiles et plus faciles. Parfois, généraliser la question la rend plus claire, dit-elle. Mais dans l'ensemble, elle n'a pas atteint la clarté : la plupart des gens pensent que P n'est pas égal à NP. Et je ne sais pas. Peut-être que c'est juste moi, mais j'ai l'impression qu'il est de moins en moins clair que c'est la vérité.

Historiquement, souligne Pitassi, des résultats surprenants sont parfois sortis de nulle part - des impossibilités semblant prouvées possibles par des concepteurs d'algorithmes intelligents. La même chose pourrait se produire avec P contre NP, peut-être dans 50 ans ou un siècle. L'un des résultats les plus importants de toute la théorie de la complexité, par exemple, a été obtenu par David Barrington, de l'Université du Massachusetts, Amherst, en 1989. L'essentiel (pour nos besoins) est qu'il a conçu un algorithme intelligent, qui décidé de faire quelque chose qui aurait apparemment dû nécessiter une quantité illimitée de mémoire, mais qui en fait utilisé une quantité étonnamment petite - seulement cinq bits d'information, assez pour spécifier un nombre entre un et 32 ​​(inclus) ou un mot de deux lettres.

Un résultat plus récent et connexe, datant de 2014, a pris James Cook par surprise. S'inspirant du théorème de Barrington, il utilise la mémoire d'une manière merveilleusement étrange. Comme l'indique le titre de l'article, par Harry Buhrman et ses collaborateurs de l'Université d'Amsterdam, il s'agit d'informatique avec une mémoire pleine. James peut débiter le paragraphe d'introduction de l'article pratiquement textuellement :

Imaginez le scénario suivant. Vous souhaitez effectuer un calcul qui nécessite plus de mémoire que celle dont vous disposez actuellement sur votre ordinateur. Une façon de résoudre ce problème consiste à installer un nouveau disque dur. Il s'avère que vous avez un disque dur mais qu'il est plein de données, d'images, de films, de fichiers, etc. Vous n'avez pas besoin d'accéder à ces données pour le moment, mais vous ne voulez pas non plus les effacer. Pouvez-vous utiliser le disque dur pour votre calcul, éventuellement en modifiant temporairement son contenu, garantissant que lorsque le calcul est terminé, le disque dur est de retour dans son état d'origine avec toutes les données intactes ?

La réponse, contre-intuitive, est oui.

James considère cela comme une mémoire empruntée. Après le choc de ce résultat, il s'est amusé à trouver comment l'appliquer à un problème particulier - reprendre là où son père s'était arrêté.

Il y a quelques décennies, Steve Cook est passé à d'autres problèmes connexes de la théorie de la complexité. Avec un problème, il a fait une conjecture sur la quantité de mémoire dont un algorithme aurait besoin pour résoudre le problème, en l'affinant au minimum absolu. En 2019, James, avec Ian Mertz, l'un des doctorants de Pitassi, a déployé l'idée poétique d'emprunter la mémoire et a prouvé qu'il fallait encore moins de mémoire. Le résultat n'a pas été jusqu'à réfuter la conjecture de son père, mais c'est quand même un peu de progrès dans la quête de la grande complexité.

Et les problèmes de la théorie de la complexité, observe James, ont parfois un effet domino - s'il y a une preuve dans un coin critique, alors tous les dominos tombent. Les résultats décisifs, les plus importants, proviennent d'une longue série de travaux, par de nombreuses personnes différentes, faisant des progrès progressifs et établissant des liens entre différentes questions, jusqu'à ce qu'un grand résultat émerge.

Il mentionne également une mise en garde : alors qu'un algorithme P = NP vraiment diaboliquement rapide serait bouleversant, il existe également un scénario dans lequel P = NP pourrait être une déception. Il pourrait s'avérer qu'un algorithme P capable de résoudre le problème NP-complet est sur une échelle de temps de, disons, n ^100. Techniquement, cela relève de P : c'est un polynôme, dit James. Mais n ^ 100 est encore très peu pratique - cela signifierait que tout problème important serait toujours hors de portée à l'échelle humaine.

C'est, bien sûr, en supposant que nous pouvons trouver l'algorithme en premier lieu. Donald Knuth, un algorithmiste à Stanford, a changé d'avis ces dernières années - il a changé d'avis. Son intuition est que P est effectivement égal à NP, mais que nous ne pourrons probablement jamais utiliser ce fait, pratiquement parlant, car nous ne connaîtrons en fait aucun des algorithmes qui fonctionnent. Il existe un nombre ahurissant d'algorithmes, explique-t-il, mais la plupart d'entre eux dépassent notre connaissance. Ainsi, alors que certains chercheurs pourraient insister sur le fait qu'aucun algorithme P = NP n'existe, Knuth soutient qu'il est plus probable qu'aucun algorithme en temps polynomial ne sera jamais incarné - en fait écrit sous forme de programme - par de simples mortels.

Pour Papadimitriou, toute réponse éteindrait une obsession de toute une vie. Il pense que le problème P contre NP appartient au domaine des énigmes scientifiques fondamentales telles que l'origine de la vie et l'unification des champs de force de la nature. C'est le genre de puzzle profond et conséquent, concret mais universel, dit-il, qui ajoute un sens non seulement à la science, mais à la vie humaine elle-même.

Imaginez que nous ayons de la chance et que nous soyons capables de tirer encore quelques milliers d'années de cette planète, contre toute attente et malgré les excentriques, a-t-il déclaré. Et nous ne résolvons pas ces problèmes. À quoi ça sert?!