Blog de Paul Jorion

Retranscription de P vs. NP, le 27 février 2021.

Bonjour, nous sommes le samedi 27 février 2021 et aujourd’hui, je ne vais pas parler de l’actualité – à moins que ça me traverse l’esprit en cours de route – je voudrais vous parler d’une actualité personnelle, de choses sur lesquelles je travaille et si vous suivez mon blog, vous avez peut-être vu qu’aux mois de janvier et mois de février, j’étais moins présent et ce n’est pas parce que je me reposais, c’est au contraire parce que je travaillais un peu davantage. Je me remettais sur des problèmes qu’on pourrait appeler de mathématiques pures et ce n’est pas moi qui y avais pensé : c’est une mathématicienne qui m’avait écrit il y a un an, en janvier 2020 et elle m’avait écrit : « Ecoutez, vous avez écrit ceci [et je vais vous dire ce que c’était] et j’ai l’impression que vous pourriez m’aider sur un problème sur lequel je travaille déjà depuis une dizaine d’années en collaboration avec d’autres : la conjecture qu’on appelle P et NP » (où on met un égal entre P et NP, ou bien on met vs. pour versus, « vis-à-vis » de, « contre », etc.).

P contre NP, face à NP etc. c’est un problème dont je ne vais même pas vous dire de quoi ça parle sauf de manière tout à fait elliptique. Et pourquoi je ne vais pas vous dire de quoi ça parle ? C’est parce que, à mon sens, la solution du problème est liée au fait qu’il a été très très mal posé au départ, peut-être pas par la personne, David Hilbert [1862-1943], qui a posé le problème le premier mais, aussitôt qu’on s’est engagé dans des tentatives de solutions, ça a été une cacophonie. Les gens ont parlé de choses différentes. On a introduit des notions comme « l’intuition pourrait nous aider ici ou là », etc. On a parlé d’un « oracle » qui connaîtrait la solution de certains problèmes et on a placé cet oracle au cœur de certaines démonstrations sous prétexte de calculer un degré de solvabilité, des choses de cet ordre-là.

Et ça me passionne ! La raison pour laquelle cette mathématicienne est entrée en contact avec moi, c’est parce que j’avais écrit quelque chose sur le blog il y a longtemps. C’était à l’époque de mon voyage en Chine, c’était en Chine même que j’avais écrit ça : j’avais parlé d’un paradoxe fameux dans la logique ancienne, antique, chinoise : « Un cheval blanc n’est pas un cheval ». C’est un paradoxe du philosophe linguiste philologue, je ne sais pas comment il faudrait l’appeler, Gongsun Long [env 320–250 av. J-C], disons « logicien » ou « philosophe », et bien entendu, c’est un paradoxe mais il explique pourquoi on pourrait penser qu’un cheval blanc n’est pas un cheval : en deux mots, parce que c’est plus qu’un cheval (c’est cheval + blanc),  parce que c’est particularisé (pas tous les chevaux : seulement ceux qui sont blancs), parce que quand on dit en chinois « cheval », c’est comme si on disait en français « du cheval » et que parler d’un cheval particulier, c’est tout à fait autre chose, et ainsi de suite.

Bien entendu, un Chinois dans la rue, à l’époque de Gongsun Long, savait qu’un cheval blanc était un cheval mais de la même manière que les philosophes grecs soulevaient des paradoxes à l’intérieur même de la logique spontanée grecque, comme Epiménide qui dit que les Crétois sont des menteurs, or, il est crétois lui-même, quel statut faut-il attribuer à ce qu’il vient de dire ? et ainsi de suite.

Dans la langue chinoise, dans le contexte chinois, d’autres types de paradoxes étaient produits et c’est une chose à laquelle j’avais déjà réfléchi. J’en avais parlé dans mon livre qui s’appelait Principes des systèmes intelligents en 1989, quand je décrivais le projet de logiciel d’intelligence artificielle que j’avais produit pour British Telecom [ANELLA], et je reparlais de ça en 2009, dans Comment la vérité et la réalité furent inventées.

Et donc, ce que j’ai dit à cette aimable personne qui m’abordait en janvier 2020 : « Je ne peux pas : je suis débordé. Je vous reviens dès que possible ». On a échangé entretemps, sur des questions diverses. Au moment de la mort d’un de ses collaborateurs, j’ai publié le texte de ce philosophe chinois sur le blog et il y a eu une discussion à ce propos-là, mais je gardais en mémoire l’idée que je recontacterais cette personne quand j’aurais le temps et c’est durant les vacances de Noël, les dernières, que j’ai renvoyé un message à cette personne, je ne sais pas, vers le 27 décembre quelque chose comme ça, en disant : « Écoutez, maintenant, je suis disponible. On peut y aller ». Et depuis ce jour-là, on turbine sur cette question.

De son côté, il y a 10 ans qu’elle travaille là-dessus. C’est un truc à s’arracher les cheveux (enfin dans l’état où c’est maintenant). Dès que j’ai commencé à débroussailler un petit peu ça, j’ai pensé à la réflexion du philosophe des sciences Paul Feyerabend [1924-1994] qui dit qu’on résout en général un problème [en histoire des sciences] en revenant à la bifurcation. Qu’est-ce qu’il voulait dire ? C’est que quand un problème se met à apparaître insoluble, c’est en fait parce qu’on est parti sur une voie de garage. On s’est engagé dans une impasse et il faut faire demi-retour et revenir à la fourche de la route où on a pris la mauvaise voie.

Ce n’est pas évident : il faut d’abord retrouver où il y avait une fourche. S’il y en a plusieurs, il faut trouver la bonne fourche, le véritable endroit où ça a dérapé et auquel il faut revenir d’abord avant de pouvoir résoudre le problème, quitte à montrer que le problème n’a jamais eu lieu, qu’il était mal formulé dès le départ, etc.

Qu’est-ce qui me permet de progresser assez vite ? Parce que j’ai déjà des notes en quantité considérable sur ce type de sujet. Pas exactement sur celui-là mais sur ce type de sujet, que j’ai tous les bouquins qu’il faut. Quand on a commencé à discuter, elle m’a dit : « Il y a beaucoup d’informations ici et là, etc. » et, à l’exception d’un livre que je viens d’acheter qui est un livre qui a paru récemment et qui est très bien fait – c’est l’ensemble de tous les articles écrits par Alan Turing qui joue un rôle essentiel dans ce problème P et NP, par deux interventions qu’il a faites (Jack Copeland (ed.) The Essential Turing, Oxford University Press 2004), à part ça, j’avais tous les bouquins qu’il fallait, que j’avais abondamment annotés. Donc il y a moyen d’aller assez rapidement.

Pourquoi j’avais déjà plein de notes ? Pourquoi j’avais déjà les bouquins nécessaires ? C’est parce que dans ce livre de 2009 qui s’appelle Comment la vérité et la réalité furent inventées, je décompose, j’analyse pas à pas, la démonstration par Gödel de son 2^ème théorème d’incomplétude, celui consacré à l’incomplétude de l’arithmétique. J’opère là une décomposition de sa démonstration. Quel est l’outil que j’utilise essentiellement ? D’abord, j’utilise deux types d’informations : celles qui me sont venues de deux de mes professeurs : Chaïm Perelman, logicien à Bruxelles (ULB), qui était mon professeur de philosophie et était un critique de la démonstration de Gödel. Il lui reprochait des incohérences. Et, par ailleurs, un autre de mes professeurs, Georges-Théodule Guilbaud, en mathématiques dans son cas, qui était mon professeur à l’École pratique des hautes études, en « mathématiques sociales » comme on appelait ça. Lui aussi avait été très critique de la démonstration de Gödel dans un autre domaine : dans le domaine des mathématiques et en particulier à propos des fonctions récursives plutôt que dans le domaine de la logique comme c’était le cas pour Perelman.

Donc, pour commencer, j’avais un excellent point de départ pour reprendre cette critique du théorème de Gödel à partir de là où mes maîtres l’avaient laissée. Par ailleurs, j’avais fréquenté à Cambridge, au séminaire d’histoire et de philosophie des sciences, Richard Braithwaite qui avait fait un très très bon petit livre d’introduction à la démonstration par Gödel de son théorème (1962) , une explication de texte. Par ailleurs, est disponible sur tout ce qui s’est passé autour de ce théorème, un excellent livre de Jean Ladrière (Les limitations internes des formalismes, 1957). Bon, c’est que des formules du début à la fin mais c’est consacré à tout ce qu’on a dit sur ce que c’est que ce théorème de Gödel, les équivalences de cette démonstration chez d’autres mathématiciens comme A. Church ou S. C. Kleene, et puis toutes les objections qui ont été faites.

Donc, avec ce matériau-là, tout ce que je viens de dire, il était possible pour moi de me colleter à cette démonstration du théorème de Gödel. Il y a un peu une histoire sur ce texte que j’ai produit. Je l’ai produit… mon commentaire, à la fin des années 90, autour de (ça devait être à l’époque, où j’ai été invité à l’Université de Californie à Irvine). J’avais un peu de temps à moi et j’ai écrit ça à ce moment-là, donc on est en 1996-1997. Ça a été accepté par la revue L’Homme où je publiais énormément d’articles, revue L’Homme fondée par Haudricourt, Lévi-Strauss, Benveniste, j’oublie encore quelques autres participants à cette entreprise [Pierre Gourou, qui fut mon professeur, André Leroi-Gourhan, Georges-Henri Rivière] et, comme à l’habitude, la revue avait accepté mon texte et il n’a jamais paru et je n’ai jamais connu l’explication. À mon avis, comme ça pouvait apparaître comme une attaque en règle contre les mathématiciens, je crois qu’ils ont eu cold feet comme on dit en anglais, on a eu peut-être un peu la pétoche de se dire : « Là, on cherche la bagarre d’une manière où on n’est peut-être pas préparé à la réaction possible ». Le fait est que j’ai discuté de cette démonstration à l’époque. J’ai en particulier été invité par Jean Lassègue à l’École normale supérieure où j’ai eu l’occasion, voilà, de défendre ma thèse devant par exemple Giuseppe Longo. Donc, des mathématiciens se sont penchés sur ce que j’ai dit et on est resté, je dirais, sur un match nul. Certains disaient : « On réfute ce que vous dites » et puis, je ne voyais pas la réfutation, je voyais une sorte de malentendu et on en est resté là. Là, on était donc, je dirais, effectivement autour de l’an 2000, je suppose que c’est autour de 1999 ou 2000 que j’ai proposé mon texte à la revue L’Homme et, bon, on en est resté là.

Ce n’était pas publié dans L’Homme et je l’ai intégré après, en 2009, quand j’ai fait ce livre sur la vérité et la réalité, j’ai ajouté une grande troisième partie sur l’histoire des mathématiques et sur ma thèse, en particulier sur le fait que les mathématiques se construisent essentiellement comme une sorte de physique en réalité, avec l’exemple tout à fait flagrant de la création du calcul infinitésimal par Leibniz et Newton et quelques autres où, comme l’évêque philosophe Berkeley l’avait bien souligné, on sacrifie bien volontiers les mathématiques pour ne pas tomber sur des résultats contradictoires par rapport à l’observation physique, c’est-à-dire que c’est la physique, en fait, qui détermine ce qui va être considéré comme de bonnes mathématiques. C’est un élément central, voilà, dans l’explication que je donne dans cette 3^e partie de ce livre. 

Alors, où est-ce que nous en sommes ? Nous en sommes à chercher les bifurcations. Il y a plusieurs bifurcations auxquelles il faut revenir. D’abord, c’est la première formulation du problème. Ensuite, deux articles très importants justement d’Alan Turing, un de 1936 et un de 1954, l’intervention d’un certain Stephen Cook avec un théorème de Cook [1971].

Voilà, il y a des endroits auxquels il faut revenir et qu’est-ce qu’on découvre-là ? On découvre essentiellement que ce qui est présenté comme des preuves ne sont pas des preuves : on présente des voies de garage comme étant des démonstrations. Je découvre, comme dans la démonstration du théorème de Gödel, des choses de qualité extrêmement différente. Ma grille d’interprétation, la grille d’interprétation que je fais pour dire que ceci est bien, ceci est mal, etc. je ne la sors pas de ma propre tête : je prends le système d’Aristote, c’est-à-dire que j’utilise l’échelle qu’Aristote a produite sur la qualité d’un argument dans une démonstration. Ce n’est pas très connu, on trouve ça peut-être dans l’ouvrage d’Octave Hamelin [Le système d’Aristote], c’est quoi 1905, un truc comme ça [correct], sinon, il faut lire l’Organon, il faut le lire d’un bout à l’autre comme je l’ai fait, l’Organon d’Aristote, c’est-à-dire un ensemble d’écrits consacrés à ce qu’on appelle aujourd’hui la logique mais aussi la linguistique, la pragmatique, la sémantique, etc. et on trouve tout ça… Il y a une boîte à outils chez Aristote en disant : « Ça, c’est un mode de preuve convainquant. Ça non. Ceci, on peut l’utiliser dans l’analytique – c’est-à-dire dans la démonstration de type mathématique. Cet autre type d’argument, on peut l’utiliser dans la conversation courante ou peut-être même dans ce qu’il appelle la dialectique, c’est-à-dire la conviction au niveau des tribunaux ou des assemblées populaires (on dirait à l’Assemblée nationale) et des choses de cet ordre-là ».

Il y a une très très bonne évaluation. Et parmi toutes ces recherches qui ont été faites par les Turing, les Kleene, les Gödel, les Church, il y a, dans leurs démonstrations, il y a des choses qui sont du niveau de la démonstration convaincante mais il y a aussi pas mal de choses qui sont au niveau de choses qu’il faudrait mettre simplement à la poubelle, beaucoup d’utilisation de « paradoxes » qui, en fait, ne sont pas des paradoxes, qui sont simplement le fait qu’on a dérapé dans le tournant et, en fait, on est dans le décor et on dit : « Ça prouve que… ». Ça ne prouve rien du tout ! Ça prouve que vous ne savez pas conduire, ça ne prouve absolument rien par rapport à [ce qu’ils affirment prouver]. L’utilisation systématique de la « preuve par l’absurde » qui, comme Aristote l’avait déjà mis en évidence, n’est pas une véritable preuve.  Vous le savez, dans le syllogisme, on a une prémisse, une proposition dont on a déterminé par ailleurs – je ne rentre pas dans les détails – qu’elle était vraie, et ensuite une autre, une seconde [prémisse dont on a déterminé par ailleurs qu’elle était vraie]. Il y a un terme moyen entre les deux et on tire une conclusion. Et Aristote avait montré, à propos de la preuve par l’absurde, que ce n’est pas du tout ça : on est dans tout à fait à autre chose. On prend un syllogisme et, à la place d’une des prémisses, on met une proposition avec laquelle on vient, qui est une hypothèse, bon, et on regarde la tête que fait le syllogisme avec cette proposition. Et si le syllogisme n’a pas l’air de tenir debout avec cette prémisse qui est en fait une hypothèse qu’on vient d’amener, on remplace cette prémisse, si ça n’a pas l’air d’aller, si quelque chose cloche, on la remplace par sa contradictoire, on la remplace par son contraire. Et là, Aristote l’avait déjà montré : qu’est-ce que c’est que le contraire de quelque chose ? Comme Hegel le disait : le contraire d’une licorne verte, c’est un hippopotame vert ou bien c’est un hippopotame rouge, ou c’est… Bon, on peut faire une liste invraisemblable de choses qui sont le « contraire » de quelque chose. On ne peut pas dire qu’on ait trouvé la seule chose, le vrai contradictoire par rapport à ce qu’on était en train de faire.

Or, dans ces démonstrations qui sont ces théorèmes sur l’incomplétude de certaines choses, voilà, sur les limitations des langages formels, on trouve des « paradoxes » qui sont, à mon sens, simplement le fait qu’on a quitté la route et l’utilisation de cette preuve par l’absurde dont je viens de rappeler que selon Aristote – et je suis tout à fait d’accord avec lui – que ça ne devrait pas… ça peut apparaître dans la rhétorique : dans la conversation de tous les jours, on peut l’utiliser, pourquoi pas, devant les tribunaux et devant les assemblées du peuple mais ça n’a rien à faire dans une démonstration mathématique.

Et là, on rejoint la préoccupation de David Hilbert qui a proposé toutes ces conjectures au départ [en 1900] : d’essayer d’éliminer des raisonnements, l’intuition des mathématiciens, qu’on travaille dans un cadre précis, qu’on connaisse les règles du jeu, du système formel dont on parle et que si on fait une réflexion de type « méta-« , comme de la méta-logique ou des méta-mathématiques, que là aussi, on ait des rambardes, que ce ne soit pas n’importe quoi, que ça ne flotte pas dans toutes les directions.

Et donc, j’ai le sentiment que sur ce P et NP, je peux faire le même type de boulot que j’ai fait sur la démonstration du théorème de Gödel, et c’est ça que je fais depuis deux mois. Alors, ça m’occupe beaucoup mais ça me fait très plaisir. Dès que j’ai une minute, je travaille là-dessus. Pourquoi ? Essentiellement parce que j’ai fait ma carrière, je dirais, entre 1987 et 2009, ce qui a été mon gagne-pain, ça a été d’écrire des programmes et, en général, écrire des programmes informatiques sur des questions qui n’avaient jamais été traitées de manière informatique donc c’était, voilà, souvent, c’était des casse-têtes. Il fallait assembler des morceaux qui venaient d’ici et là, essayer de trouver des compatibilités entre des trucs dont on n’avait jamais essayé de les mettre ensemble, et ainsi de suite, et j’aimais bien. Voilà, c’était l’activité « artistique » que je faisais, c’était de résoudre des problèmes de ce type-là et puis, en 2009, vous le savez, je me retrouve sur le pavé parce que j’avais prévu une crise qui a eu lieu effectivement. Je me suis retrouvé au cœur de cette crise et puis, bon, c’était terminé mais j’ai tout de suite rebondi si on veut en répondant à l’appel du monde extérieur, que je commente ça, que je montre ce que j’avais compris du fonctionnement de ce système financier. Et, comme j’avais une bonne maîtrise des rouages, je pouvais expliquer ça en étant chroniqueur au Monde, en étant invité à une chaire spécialement créée sur une critique de la finance à la VUB à Bruxelles et ainsi de suite. Mais là, la possibilité, je dirais, de nouveau, de me creuser les méninges sur des problèmes qui paralysent un certain nombre de gens depuis pas mal de temps, c’est très intéressant. Ça permet, comment dire, ça me permet d’utiliser des neurones que je n’utilisais pas depuis un certain temps.

Voilà, ce n’est pas du tout de l’actualité de la vie de tous les jours comme je fais d’habitude : c’est vraiment une actualité personnelle mais si je l’ai fait essentiellement, c’est pour réfléchir devant vous et pour vous demander de commenter si vous avez déjà travaillé sur ce problème. Voilà, je vais en dire des choses beaucoup plus précises que ce que j’ai dit aujourd’hui. Je vais tester aussi devant vous, sur mon blog et dans les vidéos, ce qui me semble être non seulement mon progrès mais les progrès que je fais avec cette mathématicienne. Si je ne dis pas son nom, c’est parce que j’ai pensé à faire cette vidéo ce matin et je ne lui ai pas encore posé la question de savoir si elle veut que je mentionne son nom ou non. Ce n’est pas dans un désir de secret, c’est parce que je n’ai pas encore soulevé la question. 

Voilà, allez, à bientôt, bon week-end.