P != NP selon Vinay Deolalikar

août, 9, 2010
Sylvain

Le gros buzz du moment chez les spécialistes de complexité structurelle, chez les algorithmiciens, chez les théoriciens, mais aussi chez tout ceux intéressés par les aspects un peu théorique de l’informatique, c’est l’annonce par Vinay Deolalikar d’une preuve du fait que P \neq NP. C’est une annonce, la preuve (longue de plus de 100 pages) est en cours de vérification, et ce n’est pas la première fois qu’une telle annonce est faite à tort, cependant il s’agit cette fois ci d’un chercheur sérieux dans le domaine, donc les espoirs les plus fous sont permis.

Que nous dit Vinay Deolalikar dans un mail adressé à des collègues ? il dit :

  • « I am pleased to announce a proof that P is not equal to NP »

Qu’est ce que cela signifie ?
P est la classe des problèmes de décision qui peuvent être décidés sur une machine de Turing déterministe en temps polynomial par rapport à la taille de la donnée. Cela signifie que le nombre d’étapes élémentaires pour résoudre le problème s’écrit comme un polynôme dont la variable est la taille des entrées du problème. Les problèmes qui sont dans P sont considérés comme des problèmes faciles d’un point de vue calculatoire car la puissance de calcul nécessaire pour les résoudre reste raisonnable (en pratique c’est discutable si le degré du polynôme est grand).
NP est la classedes problèmes de décision qui peuvent être décidés sur une machine de Turing NON déterministe en temps polynomial. Cela signifie qu’il existe un algorithme polynomial pour vérifier si une solution supposée est réellement une solution. Les problèmes qui sont dans NP sont donc ceux qu’on peut résoudre en vérifiant exhaustivement à l’aide d’un algo polynomial toutes les solutions possibles.
On dit souvent que le problème P =? NP revient à se poser la question de savoir si résoudre un problème est aussi facile que de vérifier si une solution en est effectivement une. Ce problème est actuellement le problème le plus important de l’informatique théorique. De nombreux aspects pratiques dépendent de ce résultat. Si P = NP, alors (par exemple), les méthodes de cryptographie actuelle ne sont pas robustes et donc fini le paiement en ligne, les transactions bancaires, la confidentialité des échanges, etc. La plupart des chercheurs pensent cependant que P \neq NP.

  • « The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof. This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible. »

Bon, là il nous dit que la preuve est drolement compliquée, avec des idées qui viennent de nombreux domaines. Et effectivement, en feuilletant le manuscrit qui est ici on a rapidement peur.

  • « This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work. »

Mais pourquoi précise t-il cela ? car l’institut Clay promet 1 million de dollar à celui qui résout le problème, sans compter Scott Aaronson qui rajoute 200000 dollars de sa poche… Et si c’est un travail corporate alors l’argent n’est pas pour lui ! Par ailleurs, si il y a une erreur, cela signifie également qu’elle est sienne, et celle de personne d’autre.

  • « Comments and suggestions for improvements to the paper are highly welcomed. »

Autrement dit, « merci de vérifier que je ne me suis pas trompé », c’est une démarche saine et totalement normale dans le milieu scientifique.

Voilà, je ferais des update au fur et à mesure de l’actualité !

Algorithms and computation, Level 2 | Comments (RSS) | 9 comments »

9 Responses to “P != NP selon Vinay Deolalikar”

Très intéressant tout ça! Est-ce qu’on a une idée du temps qu’il faudra pour vérifier cette preuve? S’il s’avère bien que P!=NP, beaucoup de spécialistes de l’informatique théorique s’en trouveront rassurés. A suivre de près en tous cas.

Caradhras, 10 août 2010 à 10:42

Cela risque d’être long, mais je pense qu’on y verra plus clair après la rentrée, car pour l’instant de nombreux spécialistes sont en mode ralenti !

Sylvain, 10 août 2010 à 10:49

Bonjour,

Si cette preuve s’avère valide, la confirmation que P!=NP va-t-elle apporter quelque chose ? Hormis, bien sûr, réfuter les conjectures des gens pensant que P=NP et permettre à certains chercheurs de passer à autre chose (je suis sûr que beaucoup ont dû s’arracher des cheveux sur cette question !) :p .

Ce que je veux dire c’est que si on avait P=NP, là le domaine de l’algorithmique évoluerait sacrément d’un coup. Autant, si P!=NP, on s’en était un peu douté et la situation actuelle ne changerait pas : pour ces foutus problèmes NP on serait toujours obligés d’avoir recours à des astuces (heuristiques, etc) pour les résoudre de la manière la plus « optimale » qui soit…

Merci pour cet article très intéressant 😉 .

jbensmai, 10 août 2010 à 14:05

Je pense qu’il y a deux aspects à prendre en compte.

1. le fait que P!=NP permettrait effectivement de passer à autre chose, et probablement renforcerait les rangs de ceux (dont je fais déja partie) qui travaillent sur les méthodes d’approximation (en passant, cela ne signifie pas forcément heuristique, il y a d’ailleurs des problèmes analogues à P=?NP pour des classes de complexité liées à l’approximation).

2. mais surtout, si la preuve est correct (à confirmer donc), elle utilise des notions venus d’autres domaines, et la comprehension fine de ses mécanismes risque de prendre du temps, et d’apporter des vues nouvelles sur la notion de calcul, de complexité, etc.

Sylvain, 10 août 2010 à 15:03

J’ai cité les heuristiques car ce sont les seuls outils liés à la résolution des problèmes NP que j’ai été amené à manipuler (je suis encore étudiant !). Mais j’ose espérer qu’effectivement, depuis le temps où l’on se casse les dents sur cette conjecture, il existe d’autres alternatives à ces dernières (d’ailleurs, si vous avez quelques pistes à me donner, je suis preneur !).

Je n’avais pas pris en compte l’apport des nouvelles notions, et de ce point de vue c’est sûr que c’est intéressant. D’ailleurs, à vous lire, ils risquent d’apporter de bonnes perspectives au domaine que la preuve soit effectivement validée ou non.

Quoi qu’il en soit, j’imagine que de nombreuses personnes doivent attendre le verdict avec impatience. Croisons les doigts pour que ce fichu mythe de P=NP se termine enfin…

jbensmai, 10 août 2010 à 15:36

Je ne sais pas quel est ton niveau de maîtrise en info théorique, mais la page wikipedia sur les algos probas donnent les bons pointeurs :

http://en.wikipedia.org/wiki/Randomized_algorithm

Notamment l’excellent livre de Motwani et Raghavan.
Sinon, les livres de Lassaigne et De Rougemont sont également très bien (mon principal coauteur pour l’un et mon directeur de thèse pour l’autre, cela ne peut pas être mauvais ;))

Sylvain, 10 août 2010 à 15:58

Je ferais deux commentaires.

1. Je regrette l’emploi dans cet article de l’anglicisme « preuve ». J’espère que Deolalikar a produit une démonstration au sens mathématique du terme, dont il faudra vérifier si elle est correcte ou non, et non pas d’une « preuve » au sens juridique ou physique du terme ou comme un objet comme la preuve par neuf qui est une vérification de la correction d’une multiplication. Consultez http://www.cnrtl.fr/lexicographie/preuve, pour un définition du mot « preuve » en français. L’emploi de « preuve » comme traduction de « proof » est d’un usage récent en français (moins de quinze ans) comme synonyme de « démonstration ».

2. Sil’on avait démontré P=NP, cela ne dirait rien sur la faisabilité des algorithmes, car on pourrait très bien avoir démontré qu’un algorithme de recherche est polynomial par une démonstration d’existence sans pouvoir exhiber le degré du polynôme exprimant la complexité, ce degré pouvant être 1 000 000 000 000 000. On ne serait guerre plus avancé. En revanche, on sait maintenant que SAT3, la référence en ce qui concerne les problèmes NP est pratiquement résoluble (voir http://dl.dropbox.com/u/2518969/PDF_de_FDI2/sat.pdf). Donc que P=NP ou que P=/=NP laisse de la place pour la recherche d’algorithmes efficaces en pratique et pour des outils d’évaluation de la complexité moins violents que la force brute dans le pire cas.

Ceci dit, si vous lisez l’anglais lisez http://www.cs.umd.edu/~gasarch/papers/poll.pdf qui est un sondage sur l’opinion en 2002 des grands scientifiques du domaine de la complexité sur la résolution de P=/=NP. Il semble que la méthode de Deolalikar est cohérente avec la majorité de ces opinions.

Pierre, 12 août 2010 à 11:03

@Pierre

je pense (malheureusement ou pas, c’est à discuter) que les enseignants-chercheurs n’ont plus vraiment la familiarité avec les termes français. Je me souviens que le jour de ma soutenance de thèse (il y a 7 ans !) Allouche et Cori m’avait fait la même remarque ! Ceci étant cela fait moins de 15 ans que je fais de la recherche, donc je suis dans les clous 😉

Personnellement, P!=NP cela fait bien mon affaire vu que je travaille sur les algos probabilistes. Ce que je trouve séduisant dans les nouvelles idées qui émergent, c’est l’utilisation de notions venues de la physique statistique, dont je découvre chaque jour par ailleurs des résultats très intéressants (et par la même occasion que mes « découvertes » ont été déja faites dans les années 70 par les physiciens :()

Sylvain, 12 août 2010 à 22:03

Je viens de lire les dernières discussions du jour sur la « preuve » de Deolalikar et il semblerait que ce ne sera pas pour ce coup là que le problème sera résolu (voir http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np/#comment-4885 ).

Sylvain, 12 août 2010 à 22:58
Picture: courtesy of Abby Blank