{"id":8829,"date":"2020-07-17T17:01:19","date_gmt":"2020-07-17T15:01:19","guid":{"rendered":"https:\/\/sciencetonnante.wordpress.com\/?p=8829"},"modified":"2020-09-01T13:39:07","modified_gmt":"2020-09-01T11:39:07","slug":"est-ce-que-p-np","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2020\/07\/17\/est-ce-que-p-np\/","title":{"rendered":"Est-ce que P = NP ?"},"content":{"rendered":"<p>La vid\u00e9o du jour s&rsquo;attaque \u00e0 un des 7 probl\u00e8mes \u00ab\u00a0\u00e0 1 million de $\u00a0\u00bb&#8230;enfin \u00ab\u00a0s&rsquo;attaque\u00a0\u00bb&#8230; fa\u00e7on de parler !<\/p>\n<p><iframe title=\"Nos algorithmes pourraient-ils \u00eatre BEAUCOUP plus rapides ? (P=NP ?)\" width=\"770\" height=\"433\" data-src=\"https:\/\/www.youtube.com\/embed\/AgtOCNCejQ8?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" class=\"lazyload\" data-load-mode=\"1\"><\/iframe><\/p>\n<h3>Les classes de complexit\u00e9<\/h3>\n<p>Il y aurait des dizaines de chose \u00e0 ajouter \u00e0 ce que j&rsquo;ai dit au sujet des classes de complexit\u00e9. Je voudrais commencer par une qui n&rsquo;est pas a priori \u00e9vidente ou tr\u00e8s connue : stricto sensu, la d\u00e9finition des classes P et NP (et la question P=NP qui va avec) ne concernent que <strong>les probl\u00e8mes de d\u00e9cision<\/strong>.<\/p>\n<p>Un probl\u00e8me de d\u00e9cision, c&rsquo;est un probl\u00e8me dont la r\u00e9ponse est \u00ab\u00a0oui\u00a0\u00bb ou \u00ab\u00a0non\u00a0\u00bb. Par exemple : est-il possible de satisfaire telle formule bool\u00e9enne ? est-il possible de remplir le sac-\u00e0-dos en respectant les contraintes de place et de butin minimal ?<!--more--><\/p>\n<p>De fait quand je prends initialement les exemples de recherche de minimum ou de tri, bien que la complexit\u00e9 des algorithmes soit polynomiale, ce ne sont v\u00e9ritablement des probl\u00e8mes de la classe P puisque ce ne sont pas des probl\u00e8mes de d\u00e9cision.<\/p>\n<p>C&rsquo;est souvent un point de confusion. Prenons l&rsquo;exemple du probl\u00e8me du voyageur de commerce. Dans sa forme traditionnelle, il s&rsquo;agit de trouver le chemin le plus court reliant un certain nombre de villes. Tel quel, \u00e7a n&rsquo;est pas un probl\u00e8me de d\u00e9cision, et surtout \u00e7a n&rsquo;est pas un probl\u00e8me dont on peut v\u00e9rifier la solution en temps polynomial ! Imaginez que je vous propose une solution. C&rsquo;est facile de calculer sa longueur, de v\u00e9rifier qu&rsquo;elle passe bien par toutes les villes&#8230;mais comment v\u00e9rifier rapidement qu&rsquo;elle est bien<em> la plus courte<\/em> ? Eh bien \u00e7a n&rsquo;est pas faisable en temps polynomial !<\/p>\n<p>Donc quand je dis que le probl\u00e8me du voyageur de commerce est NP-complet, il faut l&rsquo;entendre : dans sa version \u00ab\u00a0d\u00e9cisionnelle\u00a0\u00bb, qui est : <strong>est-il possible de trouver un chemin qui passe par toute les villes et qui soit de longueur inf\u00e9rieure \u00e0 L ?<\/strong> L\u00e0 si je vous soumets une solution, c&rsquo;est tr\u00e8s facile de v\u00e9rifier qu&rsquo;elle respecte la contrainte.<\/p>\n<p>On aurait pu tenir le m\u00eame raisonnement sur le probl\u00e8me du sac-\u00e0-dos, et sur tous les probl\u00e8mes qui se pr\u00e9sentent comme des probl\u00e8mes d&rsquo;optimisation (en recherche op\u00e9rationnelle, notamment).<\/p>\n<h3>La myst\u00e9rieuse classe NP<\/h3>\n<p>Comme je l&rsquo;ai dit dans la vid\u00e9o, il est tentant de penser que NP signifie \u00ab\u00a0non-polynomial\u00a0\u00bb. Mais il s&rsquo;agit en fait de la classe des \u00a0probl\u00e8mes de d\u00e9cision \u00ab\u00a0v\u00e9rifiables\u00a0\u00bb en temps polynomial. Evidemment, cette \u00ab\u00a0v\u00e9rifiabilit\u00e9\u00a0\u00bb ne concerne que les cas o\u00f9 la r\u00e9ponse est \u00ab\u00a0oui\u00a0\u00bb.<\/p>\n<p>(Pour les gourmands, on peut d\u00e9finir la classe co-NP qui est en gros la m\u00eame chose, mais en sym\u00e9trique : v\u00e9rifiable en temps polynomial quand la r\u00e9ponse est non. D&rsquo;ailleurs on ne sait pas si co-NP = P et\/ou co-NP=NP).<\/p>\n<p>Si on veut \u00eatre pr\u00e9cis sur la d\u00e9finition, on devrait parler de \u00ab\u00a0preuve v\u00e9rifiable en temps polynomial par une machine de Turing d\u00e9terministe\u00a0\u00bb. Et cette notion est \u00e9quivalente \u00e0 une notion plus opaque de \u00ab\u00a0r\u00e9soluble en temps polynomial par une machine de Turing non-d\u00e9terministe\u00a0\u00bb. D&rsquo;o\u00f9 le sens de l&rsquo;acronyme NP pour \u00ab\u00a0non-d\u00e9terministe polynomial\u00a0\u00bb. Sans rentrer dans les d\u00e9tails, une machine de Turing non-d\u00e9terministe est une construction de l&rsquo;esprit qui serait comme un ordinateur capable d&rsquo;essayer \u00ab\u00a0plein de solutions \u00e0 la fois\u00a0\u00bb. (Non, \u00e7a n&rsquo;est pas un ordinateur quantique !). Donc une proposition de solution est v\u00e9rifiable en temps polynomial, une hypoth\u00e9tique machine non-d\u00e9terministe qui \u00ab\u00a0essayerait toutes les solutions \u00e0 la fois\u00a0\u00bb pourrait r\u00e9soudre le probl\u00e8me en temps polynomial.<\/p>\n<h3>Parlons complexit\u00e9<\/h3>\n<p>Sur plusieurs \u00e9l\u00e9ments li\u00e9s aux complexit\u00e9s, je suis rest\u00e9 \u00e9vasif, impr\u00e9cis et j&rsquo;ai mentionn\u00e9 des complexit\u00e9s \u00ab\u00a0sous-optimales\u00a0\u00bb, car il me semble que rentrer dans des formules un peu barbares pleines de puissances et de logarithme n&rsquo;apportait pas grand chose \u00e0 l&rsquo;argument.<\/p>\n<p>Bon d\u00e9j\u00e0 j&rsquo;ai \u00e9vit\u00e9 les notations O() et o(). Je pense que \u00e7a ne manquera \u00e0 personne !<\/p>\n<p>Concernant la question du tri, j&rsquo;ai indiqu\u00e9 une borne en O(N log N), \u00e7a ne vaut que pour les tris bas\u00e9s sur la comparaison. On peut faire mieux avec des algorithmes qui fonctionnent par distribution, mais ils n\u00e9cessitent une plus grande m\u00e9moire et ne fonctionnent que pour certains types de listes \u00e0 trier.<\/p>\n<p>Et si on prend par exemple le probl\u00e8me de factorisation. Tout d&rsquo;abord j&rsquo;ai appel\u00e9 N le nombre de chiffres (sous-entendu en base 10, donc); d&rsquo;un point de vue th\u00e9orique, on se r\u00e9f\u00e8rerait plut\u00f4t au nombre de bits (base 2). Une recherche consistant \u00e0 diviser par absolument tous les nombres serait plut\u00f4t en complexit\u00e9 \\(2^N\\).<\/p>\n<p>En fait le meilleur algorithme qu&rsquo;on connaisse, le <a href=\"https:\/\/fr.wikipedia.org\/wiki\/Crible_alg\u00e9brique\" target=\"_blank\" rel=\"noopener\">crible alg\u00e9brique<\/a>\u00a0serait plut\u00f4t en \\(2^{N^{1\/3}}\\). Du fait de la racine cubique, je crois qu&rsquo;on a le droit de dire qu&rsquo;il est \u00ab\u00a0sous-exponentiel\u00a0\u00bb, mais \u00e7a reste \u00ab\u00a0non-polynomial\u00a0\u00bb. C&rsquo;est donc strictement entre polynomial et exponentiel.<\/p>\n<p>Sur les bornes inf\u00e9rieures, j&rsquo;ai argument\u00e9 par exemple que pour rechercher le minimum dans une liste il fallait au moins N op\u00e9rations, puisqu&rsquo;il faut au moins aller consid\u00e9rer une fois chaque nombre. Cela vaut avec un ordinateur classique. Avec un ordinateur quantique \u00e7a peut changer : par exemple l&rsquo;algorithme de Grover permet la recherche dans une base de taille N par un algorithme de complexit\u00e9 \\(\\sqrt{N}\\) !<\/p>\n<p>Les probl\u00e8mes r\u00e9solubles en temps polynomial par un ordinateur quantique forment leur propre classe de complexit\u00e9, appelle BQP, dont on ne sait pas tr\u00e8s bien quelle type de relation elle entretient avec les autres classes. Il se peut que certains probl\u00e8mes soient BQP mais pas NP, et que d&rsquo;autres soient NP mais pas BQP !<\/p>\n<h3>Les probl\u00e8mes NP-complet<\/h3>\n<p>J&rsquo;ai \u00e9t\u00e9 un peu vague sur ce que \u00e7a peut vouloir dire de \u00ab\u00a0ramener\u00a0\u00bb un probl\u00e8me NP \u00e0 un probl\u00e8me NP-complet. Il y a deux aspects \u00e0 cela.<\/p>\n<p>Prenons un probl\u00e8me NP avec une instance de ce probl\u00e8me de taille n : la premi\u00e8re chose c&rsquo;est que la proc\u00e9dure de r\u00e9duction (de transformation) de cette instance en une instance d&rsquo;un probl\u00e8me NP-complet doit se faire en un temps polynomial. Il faudra donc compter le temps \\(T(n)\\) de transformation (et peut-\u00eatre de transformation inverse). Si ce temps \u00e9tait exponentiel, \u00e9videmment ce serait cuit.<\/p>\n<p>Mais l&rsquo;autre aspect important, c&rsquo;est que la taille de l&rsquo;instance du probl\u00e8me NP-complet n&rsquo;est pas forc\u00e9ment la m\u00eame que \\(n\\), la taille initiale. L\u00e0 aussi on demande que la taille soit au plus un polyn\u00f4me \\(E(n)\\) de la taille de d\u00e9part. De sorte que si \\(C(.)\\) est la complexit\u00e9 du probl\u00e8me NP-complet, r\u00e9soudre le probl\u00e8me de d\u00e9part via cette transformation aura une complexit\u00e9<\/p>\n<p style=\"text-align: center;\">\\(T(n) + C(E(n))\\).<\/p>\n<p>Ici il est important que E soit un polyn\u00f4me, car si \u00e9videmment c&rsquo;est une exponentielle, \u00e7a ruinerai l&rsquo;espoir qu&rsquo;un algorithme polynomial pour un probl\u00e8me NP complet nous donne un algorithme polynomial pour n&rsquo;importe quel probl\u00e8me NP.<\/p>\n<p><em>(Merci \u00e0 mon ami Xoff qui m&rsquo;a pr\u00e9cis\u00e9 tout \u00e7a !)<\/em><\/p>\n<p>D&rsquo;ailleurs, si vous voulez un exemple concret de transformation d&rsquo;un probl\u00e8me, je vous recommande <a href=\"https:\/\/www.youtube.com\/watch?v=8TrIW-4kfRg\" target=\"_blank\" rel=\"noopener\">la vid\u00e9o de Passe-Science<\/a> o\u00f9 il montre explicitement comment mettre en correspondance un probl\u00e8me SAT et un probl\u00e8me de coloriage de graphe avec 3 couleurs (autre probl\u00e8me NP-complet).<\/p>\n<p>D&rsquo;ailleurs sur le probl\u00e8me SAT, j&rsquo;ai en fait pr\u00e9sent\u00e9 le probl\u00e8me parfois appel\u00e9 CNF-SAT, o\u00f9 CNF veut dire \u00ab\u00a0forme normale conjonctive\u00a0\u00bb. En toute g\u00e9n\u00e9ralit\u00e9, le probl\u00e8me SAT est celui qui concerne n&rsquo;importe quelle formule. Dans sa version CNF, on se limite aux formules qui sont un \u00ab\u00a0grand ET\u00a0\u00bb de sous-expressions qui sont des OU. C&rsquo;est de \u00e7a que j&rsquo;ai tir\u00e9 mon analogie de la s\u00e9lection des membres du club : chaque membre repr\u00e9sente un ensemble de OU, et on veut que chaque membre soit satisfait donc c&rsquo;est un grand ET sur tous les membres.<\/p>\n<p>Tiens d\u00e9tail amusant pour finir, que je n&rsquo;ai pas r\u00e9ussi \u00e0 caser dans la vid\u00e9o : 1-SAT et 2-SAT sont P, mais on peut d\u00e9finir 3-SAT qui est NP-complet. Je trouve \u00e7a assez remarquable de voir que 3-SAT (qui a l&rsquo;air pourtant d&rsquo;un probl\u00e8me plus r\u00e9duit que CNF-SAT ou SAT, et \u00e0 peine plus compliqu\u00e9 que 2-SAT) soit \u00ab\u00a0d\u00e9j\u00e0\u00a0\u00bb NP-complet.<\/p>\n<p>Edit du 18\/07\/2020 : Revenons sur le probl\u00e8me du sac-\u00e0-dos<\/p>\n<p>Beaucoup de gens pensent avoir trouv\u00e9 une solution au probl\u00e8me du sac-\u00e0-dos en triant les objets par \u00ab\u00a0densit\u00e9\u00a0\u00bb, c&rsquo;est \u00e0 dire \u00ab\u00a0valeur en \u20ac par kg\u00a0\u00bb. Ca donne une premi\u00e8re id\u00e9e, mais \u00e7a ne fonctionne pas.<\/p>\n<p>Voici un exemple : un sac de 50 kg, et 3 objets. L&rsquo;un de 36 kg valant 36 euros (densit\u00e9 1), et deux de 25kg valant 20 euros (densit\u00e9 0.8). Si l&rsquo;objectif est d&rsquo;atteindre 38 euros, il faut prendre les deux objets les moins denses.<\/p>\n<p>Ce petit \u00ab\u00a0contre-exemple\u00a0\u00bb est tr\u00e8s simple, mais montre que de fa\u00e7on g\u00e9n\u00e9rale, le fait d&rsquo;utiliser la densit\u00e9 ne permet pas \u00e0 coup s\u00fbr de conclure en temps polynomial. Surtout quand on commence \u00e0 mettre des objets de densit\u00e9 proche de l&rsquo;objectif.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>La vid\u00e9o du jour s&rsquo;attaque \u00e0 un des 7 probl\u00e8mes \u00ab\u00a0\u00e0 1 million de $\u00a0\u00bb&#8230;enfin \u00ab\u00a0s&rsquo;attaque\u00a0\u00bb&#8230; fa\u00e7on de parler ! Les classes de complexit\u00e9 Il y aurait des dizaines de chose \u00e0 ajouter \u00e0 ce que j&rsquo;ai dit au sujet des classes de complexit\u00e9. Je voudrais commencer par une qui n&rsquo;est pas a priori \u00e9vidente<\/p>\n","protected":false},"author":1,"featured_media":8908,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[45,4],"tags":[],"class_list":{"0":"post-8829","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-informatique","8":"category-mathematiques"},"jetpack_featured_media_url":"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2020\/07\/vignette_fond.jpg","jetpack_sharing_enabled":true,"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/8829","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/comments?post=8829"}],"version-history":[{"count":2,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/8829\/revisions"}],"predecessor-version":[{"id":8909,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/8829\/revisions\/8909"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media\/8908"}],"wp:attachment":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media?parent=8829"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/categories?post=8829"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/tags?post=8829"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}