LE DIRECT
Un mathématicien avec une calculatrice Unisonic 790R en surimpression sur le visage.

Une assomption mathématique

4 min
À retrouver dans l'émission

Un mathématicien ce n’est pas quelqu’un qui passe son temps à faire des calculs, c’est quelqu’un qui trouve des techniques pour ne pas avoir à les faire.

Un mathématicien avec une calculatrice Unisonic 790R en surimpression sur le visage.
Un mathématicien avec une calculatrice Unisonic 790R en surimpression sur le visage. Crédits : Alfred Gescheidt - Getty

Je vais vous parler aujourd’hui d’un problème auquel je ne comprends pas grand chose mais dont il se pourrait qu’il soit normal que je n’y comprenne pas grand chose. Si ce que je dis est obscur, ce sera que ce que je dis est vrai : que notre intuition est une goutte d’eau dans les eaux froides du calcul rationnel, qu’on ne peut pas, même avec beaucoup de chance, s’économiser des années de travail, ni résumer en trois minutes l’un des sujets les plus complexes du monde.

Échecs et statistique

Le 14 août dernier, Norbert Blum prépubliait sur ArXiv un article prometteur : “A solution of the P versus NP problem.” Le problème P versus NP, c’est une importante conjecture mathématique qui dit que quelle que soit la complexité d’un problème, il en existerait toujours une solution simple. Par exemple, beaucoup de théoriciens des échecs se demandent si celui qui commence ne dispose pas d’un léger avantage. De fait, on peut le montrer, de façon statistique : sur l’ensemble des parties qui se sont jouées depuis 1850, les blancs ont gagné un peu plus d’une fois sur deux — autour de 52 %. Ce n’est pas, évidemment, une démonstration. Pour le démontrer, il faudrait faire tourner sur un ordinateur l’ensemble des parties possibles. Et c’est ici qu’on trouve le NP de notre conjecture : NP ça veut dire non-polynomial, et en résumé ça signifie qu’un problème en apparence simple — il n’y a pas tellement de pièces, aux échecs, et l’échiquier n’a que 64 cases — génère une complexité explosive. Un véritable big-bang de complexité : le nombre de partie possible, connu sous le nom de nombre de Shannon, c’est autour de 10^120. Pour donner une idée le nombre d’atomes dans l’univers c’est 10^80. Cela signifie que pour avoir la réponse à notre question, connaître l’avantage réel des blancs, même un ordinateur de taille cosmique serait insuffisant. Sauf si P = NP, justement, et que les problèmes à tendance lourdement exponentielle pourraient être réduits à des problèmes plus simples. Autrement si on pouvait démontrer notre conjecture en un nombre raisonnable d’étapes.

Nous sommes des êtres intuitifs

Si P = NP, cela voudrait dire, en fait, qu’il existerait des solutions économiques à tous les problèmes connus — des sortes de raccourcis dans les mathématiques. Et c’est je crois quelque chose auquel les mathématiciens croient spontanément : un mathématicien ce n’est pas quelqu’un qui passe son temps à faire des calculs, c’est quelqu’un qui trouve des techniques pour ne pas avoir à les faire. Il existe d’ailleurs des équations d’une sophistication délirante que nous savons résoudre de façon intuitive : modéliser correctement une main avec tous ses muscles, aucun ordinateur n’y arrive encore, mais notre cerveau sait le faire. Nous sommes des êtres intuitifs. Nous vivons dans un monde finalement assez simple. A moins que l’évolution, ce très gros ordinateur biologique, ait réduit la plupart des problèmes complexes de notre environnement, les problèmes NP, à des problèmes intuitifs, les problèmes P, pour nous rendre la vie plus agréable. Notre niche écologique principale serait alors un biais cognitif… Idée un peu pénible. Sauf, évidemment, si P = NP. Auquel cas, notre intuition serait fondée, et notre monde, non seulement serait moins cruel, mais aussi plus véritable.

P = NP, ou la grâce

L’article de Norbert Blum est paru le 14 août. J’en ai pris connaissance le 15, dans la petite église où j’étais venu, avec ma fille, pour la fête de la Mer et son irrésistible atelier origami dans la sacristie, étape obligatoire d’une procession rituelle qui devait nous conduire jusqu’à la mer, qu’un prêtre bénirait pendant que les enfants du village y jetteraient leurs bateaux en papier. Je ne crois pas en Dieu et encore moins au dessein intelligent, mais je me disais là, en lisant des recensions de l’article de Norbert Blum pour écourter la messe, que P = NP était un assez bel équivalent de la grâce, et j’avais secrètement envie que l’article soit faux. Il le serait, aux dernières nouvelles, mais Norbert Blum n’a pas abandonné la partie. Dans un court article daté du 11 octobre, il reconnaît sa défaite, mais annonce qu’il repart à l’attaque : “Pour y parvenir, des problèmes difficiles doivent être résolus, mais je m’y attache.” Je ne comprends pas grand choses aux fonctions de Tardos, qui sont apparement le noeud du problème, mais j’ai l’impression que cette phrase, qu’on peut traduire ainsi : “si par miracle P = NP alors j’ai une petite chance de réussir à démontrer que P ≠ NP”, est d’une ironie redoutable.

Intervenants
L'équipe

France Culture

est dans l'appli Radio France
Direct, podcasts, fictions

INSTALLER OBTENIR

Newsletter

Découvrez le meilleur de France Culture

S'abonner
À venir dans ... secondes ...par......