P≠NP vrai ou faux?

En science informatique, la question de P= ou ≠NP est un vieux problème qui vaudra au découvreur de sa solution le Millénium Prize valant un million de dollars US.

C’est en apparence très simple: P représente le nombre de problèmes aisés à réaliser par un ordinateur, et NP le nombre de problèmes dont la solution est aisée à vérifier. Mais la correspondance, ou non, entre les deux n’est pas démontrée. Du moins peut être jusqu’à cette semaine alors qu’un mathématicien chercheur chez HP, Vinay Deolalikar, a publié un document de 100 pages sur le Net pour démontrer que P≠NP (P n’est pas égal à NP).

L’enjeu n’est pas marginal, car s’il s’avérait qu’effectivement P ≠ NP cela poserait une limite de principe sur la capacité de calcul des ordinateurs.

Cette publication a immédiatement généré un buzz important dans la communauté mathématicienne, avec mise en ligne de plusieurs blogs et un wiki permettant un réel travail collaboratif de validation de cette preuve.

Travail qui a mis à jour un certain nombre de problèmes avec la preuve de Deolalikar, au point qu’à l’heure actuelle la probabilité que cette preuve soit valable, même avec quelques modifications, semble extrêmement faible. Néanmoins cet évènement a montré la très grande réactivité de cette communauté scientifique rendue possible grâce à Internet. Un processus de vérification qui aurait pris des semaines à ainsi été réalisé en quelques jours de manière tout à fait transparente.

Un blog pour suivre cette affaire.

Cet aspect collaboratif, qui est autre chose que la simple réactivité du journaliste ou du blogueur publiant un billet, est à mon avis un bon modèle pour développer un réel “Internet de combat” de la société civile contre les dérives totalitaires des classes gouvernantes que nous subissons actuellement de par le monde.

Pour suivre la discussion

One comment

Leave a Reply