SAVOIRS
P est-il égal à NP ?
Kun Giidel interroge John von Neumann
Kurt Gëidel, dans une lettre retrouvée parmi ses papiers et
qu'il envoya à John von Neumann en 1956 quelques mois
avant sa mort, est le premier à avoir formulé clairement la
question « est-ce que P =NP? » en insistant sur son importance concrète en mathématiques. Il y explique que si
P = NP (sans employer cette notation, qui sera introduite
en 1972) alors bien des questions mathématiques deviendront faciles par le procédé suivant. Pour résoudre une
question ouverte Q, il suffira de rechercher parmi toutes les
démonstrations de longueur n (n un entier fixé), dans un
système donné d'écriture des démonstrations (par exemple
dans celui de la théorie des ensembles), s'il y en a une
conduisant à la réponse cherchée. S'il y en a une, on aura
résolu le problème. Si on n'en trouve pas, et que le n essayé
est assez grand, alors « il n'y aura plus de raisons sérieuses
de rester préoccupé par le problème ».
L'indécidabilité algorithmique des systèmes logiques (c'està-dire l'affirmation qu'il n'existe pas d'algorithmes indiquant, en un temps fini, pour toute formule F, si elle est
démontrable ou non dans un système fixé assez puissant)
est un résultat négatif central en logique qui fut établi dans
la décennie 1930 par Alonzo Church et Alan Turing. Pour
Kurt Gëidel, sa version concrète est l'affirmation P * NP. On
le voit, l'enjeu est capital.
La preuve que P = NP serait une surprise. Les chercheurs
sont aujourd'hui à peu près tous persuadés qu'en vérité
P * NP (plus de 80 % de ceux qui ont un avis pensent que
P * NP). Il est étrange que, bien qu'en apparence très simple,
la question résiste autant. Les recherches menées depuis plus
de quarante ans à son sujet ont peu fait avancer vers la
solution. Elles ne sont cependant pas restées totalement
vaines, car à défaut de suggérer ce qu'il faut faire, elles donnent une meilleure compréhension des raisons des échecs
et de l'inutilité de l'exploration de certaines voies.
Références
• ls P Versus NP Formai/y lndependant ? Scott Aaronson, Bulletin of the
European Association of Th eoretical Computer Science 81 , 2003.
• Th e P versus N P Problem. Stephen Cook , C lay Mathematics ln stitute,
2000 (d isponible en ligne) .
• les problèmes NP sont-ils si compliqués ? Jean-Paul Delahaye, Dossier Pour
La Science « Les grands problèmes mathématiques », 20 12.
• Math ématiques discrètes et combi11atoire . Bibliothèque Tangente 39 , 2010.
• P. NP a11d the NP-Completeness. The Basics ofComputatio11al Complexity .
Oded Go ldre ich , Ca mbridge University Press , 20 10 .
Richard Manning Karp (né en 1935).
des classes Pou NP. C'est au ssi pour
cette raison que savoir si P est identique
à NP est si important.
On e ntend dire parfois que le problème
« P = NP ? » est, des sept problèmes
récompensés par l' Institut Clay, celui
le plus susceptible d'être résolu par un
amateur. C ' es t exac t , e n ce se ns que
son énoncé est plus simple à comprendre
que ce lui des autres problèmes et qu ' il
es t e nvi sageabl e ( bi e n que pe u probable .. . ) qu ' une so luti on é lémenta ire
soit proposée demain par un géni al passionné , par exemple e n découvrant un
a lgo rithm e polyn o mi a l po ur un problè me NP-co mpl et. La s itu ation était
la même pour le grand théorème de Fermat , dont l'énoncé est compréhensible
par tou s. Cependant, comme on l' a vu ,
cela ne signifie pas que la so lution éta it
facile ! Pour le grand théorème de Fermat , d ' aill eurs, c ' est un professio nne l
qui a résolu l' é ni gme . Aujourd ' hui , on
a de série uses ra isons de cra indre que
la questi on « P = NP ?» est d ' une profo nde et ex trême diffi culté.
J.-P. D.
86 Tan9ente Hors-série n°52. Mathématiques & informatique
P est-il égal à NP ?
Kun Giidel interroge John von Neumann
Kurt Gëidel, dans une lettre retrouvée parmi ses papiers et
qu'il envoya à John von Neumann en 1956 quelques mois
avant sa mort, est le premier à avoir formulé clairement la
question « est-ce que P =NP? » en insistant sur son importance concrète en mathématiques. Il y explique que si
P = NP (sans employer cette notation, qui sera introduite
en 1972) alors bien des questions mathématiques deviendront faciles par le procédé suivant. Pour résoudre une
question ouverte Q, il suffira de rechercher parmi toutes les
démonstrations de longueur n (n un entier fixé), dans un
système donné d'écriture des démonstrations (par exemple
dans celui de la théorie des ensembles), s'il y en a une
conduisant à la réponse cherchée. S'il y en a une, on aura
résolu le problème. Si on n'en trouve pas, et que le n essayé
est assez grand, alors « il n'y aura plus de raisons sérieuses
de rester préoccupé par le problème ».
L'indécidabilité algorithmique des systèmes logiques (c'està-dire l'affirmation qu'il n'existe pas d'algorithmes indiquant, en un temps fini, pour toute formule F, si elle est
démontrable ou non dans un système fixé assez puissant)
est un résultat négatif central en logique qui fut établi dans
la décennie 1930 par Alonzo Church et Alan Turing. Pour
Kurt Gëidel, sa version concrète est l'affirmation P * NP. On
le voit, l'enjeu est capital.
La preuve que P = NP serait une surprise. Les chercheurs
sont aujourd'hui à peu près tous persuadés qu'en vérité
P * NP (plus de 80 % de ceux qui ont un avis pensent que
P * NP). Il est étrange que, bien qu'en apparence très simple,
la question résiste autant. Les recherches menées depuis plus
de quarante ans à son sujet ont peu fait avancer vers la
solution. Elles ne sont cependant pas restées totalement
vaines, car à défaut de suggérer ce qu'il faut faire, elles donnent une meilleure compréhension des raisons des échecs
et de l'inutilité de l'exploration de certaines voies.
Références
• ls P Versus NP Formai/y lndependant ? Scott Aaronson, Bulletin of the
European Association of Th eoretical Computer Science 81 , 2003.
• Th e P versus N P Problem. Stephen Cook , C lay Mathematics ln stitute,
2000 (d isponible en ligne) .
• les problèmes NP sont-ils si compliqués ? Jean-Paul Delahaye, Dossier Pour
La Science « Les grands problèmes mathématiques », 20 12.
• Math ématiques discrètes et combi11atoire . Bibliothèque Tangente 39 , 2010.
• P. NP a11d the NP-Completeness. The Basics ofComputatio11al Complexity .
Oded Go ldre ich , Ca mbridge University Press , 20 10 .
Richard Manning Karp (né en 1935).
des classes Pou NP. C'est au ssi pour
cette raison que savoir si P est identique
à NP est si important.
On e ntend dire parfois que le problème
« P = NP ? » est, des sept problèmes
récompensés par l' Institut Clay, celui
le plus susceptible d'être résolu par un
amateur. C ' es t exac t , e n ce se ns que
son énoncé est plus simple à comprendre
que ce lui des autres problèmes et qu ' il
es t e nvi sageabl e ( bi e n que pe u probable .. . ) qu ' une so luti on é lémenta ire
soit proposée demain par un géni al passionné , par exemple e n découvrant un
a lgo rithm e polyn o mi a l po ur un problè me NP-co mpl et. La s itu ation était
la même pour le grand théorème de Fermat , dont l'énoncé est compréhensible
par tou s. Cependant, comme on l' a vu ,
cela ne signifie pas que la so lution éta it
facile ! Pour le grand théorème de Fermat , d ' aill eurs, c ' est un professio nne l
qui a résolu l' é ni gme . Aujourd ' hui , on
a de série uses ra isons de cra indre que
la questi on « P = NP ?» est d ' une profo nde et ex trême diffi culté.
J.-P. D.
86 Tan9ente Hors-série n°52. Mathématiques & informatique