P != NP selon Vinay Deolalikar

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 $latex 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 ?
$latex 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 $latex 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).
$latex 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 $latex 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 $latex 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 $latex 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 $latex 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é !