ou la vie quotidienne d'un chercheur à Tokyo

Oui, sauf que cette fois c’est peut être la bonne…

Depuis deux jours, un énorme buzz a éclaté autour d’un des problèmes mathématiques les plus connus : le problème « P≠NP ? ». Pour faire très simplifié sans être technique (en fait je vais être simpliste mais j’ai pas le choix), on appelle P la classe des problèmes mathématiques facile (c-à-d rapide) à résoudre automatiquement, et NP la classe des problèmes difficiles, où on a a priori pas de méthode intelligente pour trouver une solution rapidement.

Toute les nuances se trouvent dans mon terme « a priori ». En effet, il se peut que les problèmes difficiles soient en fait faciles, car jusque là on avait pas trouvé de bonnes manières de les traiter. Il se peut aussi (hypothèses plus communément admise) que ces deux classes P et NP sont différentes, et que les problèmes difficiles resteront difficiles à jamais.

Mine de rien, cette question est l’une des plus épineuses en mathématiques. Elle a été classé par le Clay Institut comme étant l’un des 7 problèmes les plus compliqués au monde (classement toutefois un peu arbitraire), et leur résolution est récompensée d’un prix de 1 million de dollars pour chacun des problèmes.

J’ai l’habitude de voir défiler tous les ans 2 ou 3 articles disant prouver que P est différent de NP. Donc quand Yusuke, le jeune « assistant professor » avec qui je partage mon bureau au labo m’a dit ce midi devant un plat de karaage « y’a quelqu’un qui semble avoir prouvé P≠NP », j’ai pas trop tiqué et j’ai banalement lancé un « encore ? » légèrement teinté d’ironie.

Oui, mais cette fois c’est différent. L’article est en ligne depuis 5 jours. Depuis 2 jours, toutes la communauté en informatique théorique, surtout dans le domaine de la complexité algorithmique, ne parle que de ça. Les mathématiciens du domaine, en vacances d’été, doivent certainement chercher des points hotspot wifi au bord de la plage où ils se trouvent…

Le quelqu’un en question, Vinay Deolalikar, chercheur dans le privé chez HP-labs, était un parfait inconnu ne serait-ce qu’il y a trois jours. Pas beaucoup de publications en info théorique, et pas dans de grands journaux ou conférences, mais quelqu’un qui semble sérieux quand même. Tout le monde estime que son article est bien rédigé et ne manque pas de référencer les travaux déjà existants. Bien que certains points délicats ont été relevé dans la preuve, un bon nombre de chercheurs émérites et reconnus comme tel dans la communauté info théorique s’accordent à dire qu’il s’agit là d’une avancée certaine, même si la preuve ne s’avèrerait pas juste.

Car bien entendu, la preuve d’un problème de cette envergure n’est pas lisible du premier coup d’œil. Il s’agit d’un manuscrit de 103 pages bien bourrines, utilisant beaucoup de notions très différentes, et surtout extrêmement pointue, et il faudra attendre un bon petit moment pour que la communauté scientifique du domaine comprenne la preuve, y prenne du recul et finisse par estimer que oui, la preuve est juste. Personnellement, je n’ai même pas pris la peine de télécharger l’article car je sais d’avance que je ne vais rien capter. Tout ce que je sais, c’est qu’il s’agit d’une preuve par l’absurde et utilisant à outrance la théorie des modèles finis, ce qui déjà me disqualifie d’office pour comprendre ne serait-ce qu’une demi-page de ce manuscrit.

Je faisais référence au projet polymath dans un précédent billet, où des mathématiciens mettaient judicieusement à profit les nouveaux moyens de communication pour mettre en commun leurs efforts et résoudre ensemble de grands problèmes. Ben c’est un peu ce qui se passe en ce moment, et ce mouvement s’est créé spontanément. Je reste convaincu que cette manière de faire de la recherche est l’avenir.

Pour les plus courageux d’entre vous, la page de type polymath (hébergé par polymath même si cet article ne fait pas directement parti du projet polymath), où tout est bien mieux expliqué qu’ici : http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P!%3DNP_paper

Publicités

Commentaires sur: "Encore une preuve de P≠NP ?" (2)

  1. Olivier a dit:

    On voit effectivement des prétendues démonstrations décidant ce problème de temps en temps. On verra bien si cette publi passe à la postérité. J’avais vu l’année dernière un papier dans lequel l’auteur sondait les grands noms de l’informatique fondamentale et des mathématiques en leur demandant leur avis sur la question, et en particulier s’ils conjecturaient que P = NP était démontrable dans, réfutable dans ou indépendant de je-ne-sais-plus-quelle-théorie, probablement ZFC ou ZF. À défaut de faire avancer la recherche, il donnait un aperçu des intuitions actuelles.

  2. Billx a dit:

    Il fait beau, c’est déjà ça ! :P

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :