Non, ce n’est pas une erreur : il s’agit bien d’une vidéo datant d’il y a un an, que je ne vous ai pas montrée à l’époque. Si je vous la montre aujourd’hui, c’est que je suis en train en rassembler tout ce que j’ai à dire sur la conjecture P vs. NP.
De premières réflexions, précédées du sujet à propos duquel Yu Li m’avait contacté : « Un cheval blanc n’est pas un cheval », paradoxe classique proposé par le dialecticien chinois Gongsun Long [env 320–250 av. J-C]. Vous trouverez ici le texte que j’avais consacré à cela sur le blog : Un cheval blanc (chinois) n’est pas un cheval, le 5 avril 2007
La retranscription ne reprend que la deuxième partie : celle qui parle de P vs. NP.
Le 3 janvier 2021
Ce dont je veux parler maintenant, c’est donc de ma première impression d’avoir lu ce texte de la Clay Organisation, la manière dont ils nous caractérisent de manière, je dirais, intuitive donc pas de manière formelle. Il n’y a pas d’équation là-dedans, le P vs NP problem et là, je vais essayer de dire ce que je comprends et de dire où il me semble, a priori, qu’il y a des difficultés, qu’il y a des difficultés dans la manière dont le problème est posé.
Je vais donner ma première impression parce que je sais bien, quand je regarde les choses que j’ai écrites sur un sujet qui m’est tout à fait neuf, dans ma première impression, il y a des choses que je reprends par la suite et qui me paraissent importantes et qui, peut-être, sont des choses qui ont échappé à d’autres personnes.
Donc, dans la manière dont ce problème est posé, il nous est dit qu’il a été posé pour la première fois de manière simultanée par Stephen Cook et par Leonid Levin en 1971. On ne nous dit pas exactement comment ils ont posé le problème mais moi, je vais prendre simplement ce que je vois là et qui est donc cette caractérisation du problème à partir d’un exemple particulier : comment organiser l’hébergement de 400 étudiants dont on ne peut héberger en réalité que 100 et avec une contrainte – ce que j’appelle une contrainte – c’est qu’on ne peut pas mettre dans le même espace deux personnes dont la liste a été établie par ailleurs. Bon, alors, on nous dit que c’est un exemple de manière typique de problème non P. Et pourquoi c’est un exemple typique de problème non P dit-on ? Parce qu’il est facile de vérifier si les contraintes sont remplies, sont respectées. C’est facile de le faire, je crois comprendre, par un être humain et alors qu’un ordinateur, on va dire une machine, ne pourrait pas faire comme un être humain et devrait essayer de résoudre le problème from scratch, à partir de rien, d’une manière qui fait que le calcul impliquerait des opérations plus importantes en nombre que le nombre d’atomes dans l’univers, etc., et je vois que c’est une chose à laquelle ces mathématiciens, en informatique théorique, font souvent appel : c’est de dire « un nombre d’années plus grand que la durée de l’univers », « un nombre plus grand que le nombre d’atomes » … c’est une chose qui semble les impressionner. Ils font intervenir – je le dis tout de suite – des considérations de physique ou de cosmologie même comme étant un critère. Moi, ça ne me paraît pas, en tant qu’anthropologue, philosophe, ce n’est pas un critère qui me paraît un critère solide. De la même manière quand ils disent « compliqué » ou « très dur, très difficile à faire », tout ça, ce sont des considérations d’ordre pragmatique et je ne vois pas ce que ça vient trop faire là-dedans (Turing dit des choses de ce genre – relever où).
Je vois bien qu’il y a une comparaison établie entre ce que la machine pourrait faire, qui serait très très long et très compliqué et qui dépasserait les limites de l’univers, et puis ce qu’un être humain peut faire lui, par une simple comparaison entre le résultat obtenu et celui visé, par une simple vérification. Donc, il y a cette idée, d’un côté, de calcul, et la machine, apparemment, à ce qu’on nous dit, ne peut faire que des calculs et puis il y a quelque chose qui est une vérification et dont on nous dit que c’est quelque chose qui est souvent très simple pour un être humain. [Exemple : trouver dans une liste de 1000 nombres, les seuls 17 dont le total fait 254. Il est très facile en effet d’examiner les 17 qu’on nous montre et de vérifier que leur total fait 254, mais vérifier qu’ils sont les seuls 17 sur les 1000 est aussi compliqué que de résoudre le problème initial].
Donc, je lis déjà là-dedans une représentation dualiste de type, je dirais, classique en Occident, c’est-à-dire que l’homme a une âme et n’est pas simplement matériel et que cette âme lui permet de faire des choses que la machine ne peut pas faire. Je vois souvent chez Penrose des choses de cet ordre-là, cette idée qu’il y a quelque chose de plus, qui est l’esprit. Et alors, chez lui, cette idée qu’il y a des effets quantiques dans des tubules qui constituent l’armature des neurones qui expliquent comment l’esprit peut en fait connecter avec la matière.
Moi, je suis un matérialiste et donc, quand je vois les choses comme ça, tout de suite, je tique, je sursaute, je me dis : « Qu’est-ce que c’est que cette histoire, qu’est-ce qu’on essaye de nous dire ? ». Par ailleurs, je suis un informaticien, j’ai fait beaucoup de programmation et quand on me dit : « L’être humain peut faire un processus de vérification que la machine ne peut pas faire », là aussi, je réagis. Je me dis : « Non, moi je peux… ». Si le problème, c’est de comparer deux listes, je peux moi vous faire un logiciel qui compare deux listes, je peux le faire aussi. Cela implique peut-être qu’il y ait un système de capteurs qui fassent que la machine soit un robot d’une certaine manière, qu’elle lise un texte, qu’elle traduise ce texte sous une forme utilisable numérique, qu’on puisse réduire à une suite de 0 et de 1 et, par conséquent, je ne vois pas pourquoi on me dit que la machine ne peut apparemment faire que des calculs, extrêmement mécaniques et sans la moindre réflexion et qu’un être humain peut faire quelque chose de très différent. Moi, il me semble que je peux, si on me dit qu’il y a une procédure, un processus de vérification que les humains font et qui est beaucoup plus rapide que ce que fait la machine de son côté, je dis : « Je vais vous faire moi, un logiciel qui fait ce que fait l’être humain et qui ira beaucoup plus vite que ce que fait l’être humain puisqu’il ira à la vitesse de 200 000 km à la seconde » à l’intérieur d’un ordinateur puisque ça va un peu plus lentement que la vitesse de la lumière mais moi, je peux vous écrire un logiciel qui fera la même chose que l’être humain.
Donc cette différence entre les deux, entre le processus de vérification et le processus de calcul, il me semble qu’on renvoie à ça comme étant, d’un côté, pour la machine, des machines de Turing déterministes et cette idée d’une procédure de type humain qui impliquerait éventuellement qu’on s’arrête, qu’on regarde quelque chose, qu’on reparte, etc., il me semble qu’on caractérise ça comme étant une machine de Turing non-déterministe, c’est-à-dire que cette intuition de l’humain… Il y a cette idée sous-jacente – et je crois que je vais m’arrêter là – il y a cette idée sous-jacente que je vois déjà qu’une machine est apparentée à une machine de Turing déterministe et que l’être humain, parce qu’il a un esprit, parce qu’il a une âme – ce n’est pas dit comme ça explicitement mais on le voit apparaître en arrière-plan – parce qu’il a une âme, parce qu’il a un esprit, ne pourrait être « émulé » comme on dit en informatique, il ne pourrait être émulé que par une machine de Turing non-déterministe.
Laisser un commentaire