'P vs NP' est considéré comme étant la plus grande question en suspens de tous les temps dans le domaine de l'informatique. Il s'agit de répondre à la question suivante: est ce que chaque problème simple, c'est à dire auquel on peut répondre par oui ou par non, peut être résolu rapidement par un ordinateur. 'P' signifie 'Polynomial' et correspond au temps de résolution d'un problème dont la réponse est oui ou non. Ce temps peut être calculé par une équation de type polynomiale.
Or Vinay Deolalikar des laboratoires de Hewlett-Packard situés à Palo Alto en Californie semble avoir trouvé la solution à ce problème. Il y a une semaine il a mis à disposition sur internet son rapport de cent pages censés démontrer que P est différent de NP. Et il s'apprête donc à empocher les $1 millions de dollars du Millenium Prize promis par le MIT (Massachusetts Institute of Technology) à quiconque trouverait la solution à ce problème.
Les discussions vont bon train sur les forums relatifs à 'P vs NP', et c'est Neil Immerman de l'université du Massachusetts qui pense avoir trouver une faille dans le rapport de Deolailikar. Il pense que l'erreur vient de la description réductrice de l'ensemble P. Deolailikar essaie en effet de démontrer que certains problèmes sont dans P mais pas dans NP et donc que P est différent de NP. Et pour cela il utilise un autre ensemble mathématique connu sous le nom de FO(LFP). Or son utilisation serait incohérente avec les autres méthodes employées dans le reste de la démonstration.
On ne sait pas encore si Deolalikar pourra argumenter face à cette brèche dans sa démonstration, s'il devra faire des aménagements mineurs à son argumentaire ou bien si toute sa démonstration tombera à l'eau.
Toujours est il que s'il s'avère vrai que P est différent de NP, cela signifierait que les ordinateurs seront bien plus limités que ce qu'on pensait dans les calculs complexes notamment.
/fdata%2F3906760%2Favatar-blog-1162240417-tmpphpVLzBYh.jpeg){kind=avatar}