Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
13 août 2010 5 13 /08 /août /2010 23:54

p-np.jpg


'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.

Partager cet article

Repost 0
Published by geek4u - dans Sciences
commenter cet article

commentaires

Accueil

  • : Le blog de 4ugeek.over-blog.com
  • Le blog de 4ugeek.over-blog.com
  • : Des news pour les geeks et autres nerds, et les autres. De l'info High Tech, cinéma, jeux vidéo...
  • Contact

Recherche

Archives

Catégories