{"id":131179,"date":"2022-01-04T17:42:46","date_gmt":"2022-01-04T16:42:46","guid":{"rendered":"https:\/\/www.pauljorion.com\/blog\/?p=131179"},"modified":"2022-01-04T17:44:10","modified_gmt":"2022-01-04T16:44:10","slug":"video-p-vs-np-premieres-reflexions-le-3-janvier-2021-retranscription-partielle","status":"publish","type":"post","link":"https:\/\/www.pauljorion.com\/blog\/2022\/01\/04\/video-p-vs-np-premieres-reflexions-le-3-janvier-2021-retranscription-partielle\/","title":{"rendered":"Vid\u00e9o &#8211; <b>P vs. NP &#8211; Premi\u00e8res r\u00e9flexions<\/b>, le 3 janvier 2021 &#8211; Retranscription partielle"},"content":{"rendered":"<p>Non, ce n&rsquo;est pas une erreur : il s&rsquo;agit bien d&rsquo;une vid\u00e9o datant d&rsquo;il y a un an, que je ne vous ai pas montr\u00e9e \u00e0 l&rsquo;\u00e9poque. Si je vous la montre aujourd&rsquo;hui, c&rsquo;est que je suis en train en rassembler tout ce que j&rsquo;ai \u00e0 dire sur la conjecture P vs. NP.<\/p>\n<p>De premi\u00e8res r\u00e9flexions, pr\u00e9c\u00e9d\u00e9es du sujet \u00e0 propos duquel Yu Li m&rsquo;avait contact\u00e9 : \u00ab\u00a0Un cheval blanc n&rsquo;est pas un cheval\u00a0\u00bb, paradoxe classique propos\u00e9 par le dialecticien chinois Gongsun Long [env 320\u2013250 av. J-C].\u00a0Vous trouverez ici le texte que j&rsquo;avais consacr\u00e9 \u00e0 cela sur le blog : <a href=\"https:\/\/www.pauljorion.com\/blog\/2007\/04\/05\/un-cheval-blanc-chinois-nest-pas-un-cheval\/\" target=\"_blank\" rel=\"noopener\"><b>Un cheval blanc (chinois) n\u2019est pas un cheval<\/b><\/a>, le 5 avril 2007<\/p>\n<p>La retranscription ne reprend que la deuxi\u00e8me partie : celle qui parle de P vs. NP.<\/p>\n<p><iframe loading=\"lazy\" class=\"aligncenter\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/_t33gujB_cQ\" width=\"700\" height=\"450\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><br \/>\n<!--more--><br \/>\n<b>Le 3 janvier 2021<\/b><\/p>\n<p>Ce dont je veux parler maintenant, c\u2019est donc de ma premi\u00e8re impression d\u2019avoir lu ce texte de la\u00a0Clay Organisation, la mani\u00e8re dont ils nous caract\u00e9risent de mani\u00e8re, je dirais, intuitive donc pas de mani\u00e8re formelle. Il n\u2019y a pas d\u2019\u00e9quation l\u00e0-dedans, le P vs NP problem et l\u00e0, je vais essayer de dire ce que je comprends et de dire o\u00f9 il me semble, a priori, qu\u2019il y a des difficult\u00e9s, qu\u2019il y a des difficult\u00e9s dans la mani\u00e8re dont le probl\u00e8me est pos\u00e9.<span class=\"Apple-converted-space\">\u00a0<\/span><\/p>\n<p>Je vais donner ma premi\u00e8re impression parce que je sais bien, quand je regarde les choses que j\u2019ai \u00e9crites sur un sujet qui m\u2019est tout \u00e0 fait neuf, dans ma premi\u00e8re impression, il y a des choses que je reprends par la suite et qui me paraissent importantes et qui, peut-\u00eatre, sont des choses qui ont \u00e9chapp\u00e9 \u00e0 d\u2019autres personnes.<span class=\"Apple-converted-space\">\u00a0<\/span><\/p>\n<p>Donc, dans la mani\u00e8re dont ce probl\u00e8me est pos\u00e9, il nous est dit qu\u2019il a \u00e9t\u00e9 pos\u00e9 pour la premi\u00e8re fois de mani\u00e8re simultan\u00e9e par Stephen Cook et par Leonid Levin en 1971. On ne nous dit pas exactement comment ils ont pos\u00e9 le probl\u00e8me mais moi, je vais prendre simplement ce que je vois l\u00e0 et qui est donc cette caract\u00e9risation du probl\u00e8me \u00e0 partir d\u2019un exemple particulier\u00a0: comment organiser l\u2019h\u00e9bergement de 400 \u00e9tudiants dont on ne peut h\u00e9berger en r\u00e9alit\u00e9 que 100 et avec une contrainte &#8211; ce que j\u2019appelle une contrainte &#8211; c\u2019est qu\u2019on ne peut pas mettre dans le m\u00eame espace deux personnes dont la liste a \u00e9t\u00e9 \u00e9tablie par ailleurs. Bon, alors, on nous dit que c\u2019est un exemple de mani\u00e8re typique de probl\u00e8me non P. Et pourquoi c\u2019est un exemple typique de probl\u00e8me non P dit-on\u00a0? Parce qu\u2019il est facile de v\u00e9rifier si les contraintes sont remplies, sont respect\u00e9es. C\u2019est facile de le faire, je crois comprendre, par un \u00eatre humain et alors qu\u2019un ordinateur, on va dire une machine, ne pourrait pas faire comme un \u00eatre humain et devrait essayer de r\u00e9soudre le probl\u00e8me<i> from scratch<\/i>, \u00e0 partir de rien, d\u2019une mani\u00e8re qui fait que le calcul impliquerait des op\u00e9rations plus importantes en nombre que le nombre d\u2019atomes dans l\u2019univers, etc., et je vois que c\u2019est une chose \u00e0 laquelle ces math\u00e9maticiens, en informatique th\u00e9orique, font souvent appel : c\u2019est de dire\u00a0\u00ab\u00a0un nombre d\u2019ann\u00e9es plus grand que la dur\u00e9e de l\u2019univers\u00a0\u00bb, \u00ab\u00a0un nombre plus grand que le nombre d\u2019atomes\u00a0\u00bb \u2026 c\u2019est une chose qui semble les impressionner. Ils font intervenir &#8211; je le dis tout de suite &#8211; des consid\u00e9rations de physique ou de cosmologie m\u00eame comme \u00e9tant un crit\u00e8re. Moi, \u00e7a ne me para\u00eet pas, en tant qu\u2019anthropologue, philosophe, ce n\u2019est pas un crit\u00e8re qui me para\u00eet un crit\u00e8re solide. De la m\u00eame mani\u00e8re quand ils disent \u00ab\u00a0compliqu\u00e9\u00a0\u00bb ou \u00ab\u00a0tr\u00e8s dur, tr\u00e8s difficile \u00e0 faire\u00a0\u00bb, tout \u00e7a, ce sont des consid\u00e9rations d\u2019ordre pragmatique et je ne vois pas ce que \u00e7a vient trop faire l\u00e0-dedans (Turing dit des choses de ce genre &#8211; relever o\u00f9).<span class=\"Apple-converted-space\">\u00a0<\/span><\/p>\n<p>Je vois bien qu\u2019il y a une comparaison \u00e9tablie entre ce que la machine pourrait faire, qui serait tr\u00e8s tr\u00e8s long et tr\u00e8s compliqu\u00e9 et qui d\u00e9passerait les limites de l\u2019univers, et puis ce qu\u2019un \u00eatre humain peut faire lui, par une simple comparaison entre le r\u00e9sultat obtenu et celui vis\u00e9, par une simple v\u00e9rification. Donc, il y a cette id\u00e9e, d\u2019un c\u00f4t\u00e9, de calcul, et la machine, apparemment, \u00e0 ce qu\u2019on nous dit, ne peut faire que des calculs et puis il y a quelque chose qui est une v\u00e9rification et dont on nous dit que c\u2019est quelque chose qui est souvent tr\u00e8s simple pour un \u00eatre humain. [Exemple : trouver dans une liste de 1000 nombres, les seuls 17 dont le total fait 254. Il est tr\u00e8s facile en effet d\u2019examiner les 17 qu\u2019on nous montre et de v\u00e9rifier que leur total fait 254, mais v\u00e9rifier qu\u2019ils sont les seuls 17 sur les 1000 est aussi compliqu\u00e9 que de r\u00e9soudre le probl\u00e8me initial].<\/p>\n<p>Donc, je lis d\u00e9j\u00e0 l\u00e0-dedans une repr\u00e9sentation dualiste de type, je dirais, classique en Occident, c\u2019est-\u00e0-dire que l\u2019homme a une \u00e2me et n\u2019est pas simplement mat\u00e9riel et que cette \u00e2me lui permet de faire des choses que la machine ne peut pas faire. Je vois souvent chez Penrose des choses de cet ordre-l\u00e0, cette id\u00e9e qu\u2019il y a quelque chose de plus, qui est l\u2019esprit. Et alors, chez lui, cette id\u00e9e qu\u2019il y a des effets quantiques dans des tubules qui constituent l\u2019armature des neurones qui expliquent comment l\u2019esprit peut en fait connecter avec la mati\u00e8re.<span class=\"Apple-converted-space\">\u00a0<\/span><\/p>\n<p>Moi, je suis un mat\u00e9rialiste et donc, quand je vois les choses comme \u00e7a, tout de suite, je tique, je sursaute, je me dis\u00a0: \u00ab\u00a0Qu\u2019est-ce que c\u2019est que cette histoire, qu\u2019est-ce qu\u2019on essaye de nous dire\u00a0?\u00a0\u00bb. Par ailleurs, je suis un informaticien, j\u2019ai fait beaucoup de programmation et quand on me dit\u00a0: \u00ab\u00a0L\u2019\u00eatre humain peut faire un processus de v\u00e9rification que la machine ne peut pas faire\u00a0\u00bb, l\u00e0 aussi, je r\u00e9agis. Je me dis\u00a0: \u00ab\u00a0Non, moi je peux\u2026\u00a0\u00bb. Si le probl\u00e8me, c\u2019est de comparer deux listes, je peux moi vous faire un logiciel qui compare deux listes, je peux le faire aussi. Cela implique peut-\u00eatre qu\u2019il y ait un syst\u00e8me de capteurs qui fassent que la machine soit un robot d\u2019une certaine mani\u00e8re, qu\u2019elle lise un texte, qu\u2019elle traduise ce texte sous une forme utilisable num\u00e9rique, qu\u2019on puisse r\u00e9duire \u00e0 une suite de 0 et de 1 et, par cons\u00e9quent, je ne vois pas pourquoi on me dit que la machine ne peut apparemment faire que des calculs, extr\u00eamement m\u00e9caniques et sans la moindre r\u00e9flexion et qu\u2019un \u00eatre humain peut faire quelque chose de tr\u00e8s diff\u00e9rent. Moi, il me semble que je peux, si on me dit qu\u2019il y a une proc\u00e9dure, un processus de v\u00e9rification que les humains font et qui est beaucoup plus rapide que ce que fait la machine de son c\u00f4t\u00e9, je dis\u00a0: \u00ab\u00a0Je vais vous faire moi, un logiciel qui fait ce que fait l\u2019\u00eatre humain et qui ira beaucoup plus vite que ce que fait l\u2019\u00eatre humain puisqu\u2019il ira \u00e0 la vitesse de 200\u00a0000 km \u00e0 la seconde\u00a0\u00bb \u00e0 l\u2019int\u00e9rieur d\u2019un ordinateur puisque \u00e7a va un peu plus lentement que la vitesse de la lumi\u00e8re mais moi, je peux vous \u00e9crire un logiciel qui fera la m\u00eame chose que l\u2019\u00eatre humain.<span class=\"Apple-converted-space\">\u00a0<\/span><\/p>\n<p>Donc cette diff\u00e9rence entre les deux, entre le processus de v\u00e9rification et le processus de calcul, il me semble qu\u2019on renvoie \u00e0 \u00e7a comme \u00e9tant, d\u2019un c\u00f4t\u00e9, pour la machine, des machines de Turing d\u00e9terministes et cette id\u00e9e d\u2019une proc\u00e9dure de type humain qui impliquerait \u00e9ventuellement qu\u2019on s\u2019arr\u00eate, qu\u2019on regarde quelque chose, qu\u2019on reparte, etc., il me semble qu\u2019on caract\u00e9rise \u00e7a comme \u00e9tant une machine de Turing non-d\u00e9terministe, c\u2019est-\u00e0-dire que cette intuition de l\u2019humain\u2026 Il y a cette id\u00e9e sous-jacente &#8211; et je crois que je vais m\u2019arr\u00eater l\u00e0 &#8211; il y a cette id\u00e9e sous-jacente que je vois d\u00e9j\u00e0 qu\u2019une machine est apparent\u00e9e \u00e0 une machine de Turing d\u00e9terministe et que l\u2019\u00eatre humain, parce qu\u2019il a un esprit, parce qu\u2019il a une \u00e2me &#8211; ce n\u2019est pas dit comme \u00e7a explicitement mais on le voit appara\u00eetre en arri\u00e8re-plan &#8211; parce qu\u2019il a une \u00e2me, parce qu\u2019il a un esprit, ne pourrait \u00eatre \u00ab\u00a0\u00e9mul\u00e9\u00a0\u00bb comme on dit en informatique, il ne pourrait \u00eatre \u00e9mul\u00e9 que par une machine de Turing non-d\u00e9terministe.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Non, ce n&rsquo;est pas une erreur : il s&rsquo;agit bien d&rsquo;une vid\u00e9o datant d&rsquo;il y a un an, que je ne vous ai pas montr\u00e9e \u00e0 l&rsquo;\u00e9poque. Si je vous la montre aujourd&rsquo;hui, c&rsquo;est que je suis en train en rassembler tout ce que j&rsquo;ai \u00e0 dire sur la conjecture P vs. NP.<\/p>\n<p>De premi\u00e8res [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4965,16],"tags":[7964,7936,8554],"class_list":["post-131179","post","type-post","status-publish","format-standard","hentry","category-logique","category-mathematiques","tag-gongsun-long","tag-p-vs-np","tag-un-cheval-blanc-nest-pas-un-cheval"],"_links":{"self":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts\/131179","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/comments?post=131179"}],"version-history":[{"count":4,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts\/131179\/revisions"}],"predecessor-version":[{"id":131183,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts\/131179\/revisions\/131183"}],"wp:attachment":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/media?parent=131179"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/categories?post=131179"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/tags?post=131179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}