Est-ce que P = NP ?

La vidéo du jour s’attaque à un des 7 problèmes « à 1 million de $ »…enfin « s’attaque »… façon de parler !

Les classes de complexité

Il y aurait des dizaines de chose à ajouter à ce que j’ai dit au sujet des classes de complexité. Je voudrais commencer par une qui n’est pas a priori évidente ou très connue : stricto sensu, la définition des classes P et NP (et la question P=NP qui va avec) ne concernent que les problèmes de décision.

Un problème de décision, c’est un problème dont la réponse est « oui » ou « non ». Par exemple : est-il possible de satisfaire telle formule booléenne ? est-il possible de remplir le sac-à-dos en respectant les contraintes de place et de butin minimal ?

De fait quand je prends initialement les exemples de recherche de minimum ou de tri, bien que la complexité des algorithmes soit polynomiale, ce ne sont véritablement des problèmes de la classe P puisque ce ne sont pas des problèmes de décision.

C’est souvent un point de confusion. Prenons l’exemple du problème du voyageur de commerce. Dans sa forme traditionnelle, il s’agit de trouver le chemin le plus court reliant un certain nombre de villes. Tel quel, ça n’est pas un problème de décision, et surtout ça n’est pas un problème dont on peut vérifier la solution en temps polynomial ! Imaginez que je vous propose une solution. C’est facile de calculer sa longueur, de vérifier qu’elle passe bien par toutes les villes…mais comment vérifier rapidement qu’elle est bien la plus courte ? Eh bien ça n’est pas faisable en temps polynomial !

Donc quand je dis que le problème du voyageur de commerce est NP-complet, il faut l’entendre : dans sa version « décisionnelle », qui est : est-il possible de trouver un chemin qui passe par toute les villes et qui soit de longueur inférieure à L ? Là si je vous soumets une solution, c’est très facile de vérifier qu’elle respecte la contrainte.

On aurait pu tenir le même raisonnement sur le problème du sac-à-dos, et sur tous les problèmes qui se présentent comme des problèmes d’optimisation (en recherche opérationnelle, notamment).

La mystérieuse classe NP

Comme je l’ai dit dans la vidéo, il est tentant de penser que NP signifie « non-polynomial ». Mais il s’agit en fait de la classe des  problèmes de décision « vérifiables » en temps polynomial. Evidemment, cette « vérifiabilité » ne concerne que les cas où la réponse est « oui ».

(Pour les gourmands, on peut définir la classe co-NP qui est en gros la même chose, mais en symétrique : vérifiable en temps polynomial quand la réponse est non. D’ailleurs on ne sait pas si co-NP = P et/ou co-NP=NP).

Si on veut être précis sur la définition, on devrait parler de « preuve vérifiable en temps polynomial par une machine de Turing déterministe ». Et cette notion est équivalente à une notion plus opaque de « résoluble en temps polynomial par une machine de Turing non-déterministe ». D’où le sens de l’acronyme NP pour « non-déterministe polynomial ». Sans rentrer dans les détails, une machine de Turing non-déterministe est une construction de l’esprit qui serait comme un ordinateur capable d’essayer « plein de solutions à la fois ». (Non, ça n’est pas un ordinateur quantique !). Donc une proposition de solution est vérifiable en temps polynomial, une hypothétique machine non-déterministe qui « essayerait toutes les solutions à la fois » pourrait résoudre le problème en temps polynomial.

Parlons complexité

Sur plusieurs éléments liés aux complexités, je suis resté évasif, imprécis et j’ai mentionné des complexités « sous-optimales », car il me semble que rentrer dans des formules un peu barbares pleines de puissances et de logarithme n’apportait pas grand chose à l’argument.

Bon déjà j’ai évité les notations O() et o(). Je pense que ça ne manquera à personne !

Concernant la question du tri, j’ai indiqué une borne en O(N log N), ça ne vaut que pour les tris basés sur la comparaison. On peut faire mieux avec des algorithmes qui fonctionnent par distribution, mais ils nécessitent une plus grande mémoire et ne fonctionnent que pour certains types de listes à trier.

Et si on prend par exemple le problème de factorisation. Tout d’abord j’ai appelé N le nombre de chiffres (sous-entendu en base 10, donc); d’un point de vue théorique, on se réfèrerait plutôt au nombre de bits (base 2). Une recherche consistant à diviser par absolument tous les nombres serait plutôt en complexité 2^N.

En fait le meilleur algorithme qu’on connaisse, le crible algébrique serait plutôt en 2^{N^{1/3}}. Du fait de la racine cubique, je crois qu’on a le droit de dire qu’il est « sous-exponentiel », mais ça reste « non-polynomial ». C’est donc strictement entre polynomial et exponentiel.

Sur les bornes inférieures, j’ai argumenté par exemple que pour rechercher le minimum dans une liste il fallait au moins N opérations, puisqu’il faut au moins aller considérer une fois chaque nombre. Cela vaut avec un ordinateur classique. Avec un ordinateur quantique ça peut changer : par exemple l’algorithme de Grover permet la recherche dans une base de taille N par un algorithme de complexité \sqrt{N} !

Les problèmes résolubles en temps polynomial par un ordinateur quantique forment leur propre classe de complexité, appelle BQP, dont on ne sait pas très bien quelle type de relation elle entretient avec les autres classes. Il se peut que certains problèmes soient BQP mais pas NP, et que d’autres soient NP mais pas BQP !

Les problèmes NP-complet

J’ai été un peu vague sur ce que ça peut vouloir dire de « ramener » un problème NP à un problème NP-complet. Il y a deux aspects à cela.

Prenons un problème NP avec une instance de ce problème de taille n : la première chose c’est que la procédure de réduction (de transformation) de cette instance en une instance d’un problème NP-complet doit se faire en un temps polynomial. Il faudra donc compter le temps T(n) de transformation (et peut-être de transformation inverse). Si ce temps était exponentiel, évidemment ce serait cuit.

Mais l’autre aspect important, c’est que la taille de l’instance du problème NP-complet n’est pas forcément la même que n, la taille initiale. Là aussi on demande que la taille soit au plus un polynôme E(n) de la taille de départ. De sorte que si C(.) est la complexité du problème NP-complet, résoudre le problème de départ via cette transformation aura une complexité

T(n) + C(E(n)).

Ici il est important que E soit un polynôme, car si évidemment c’est une exponentielle, ça ruinerai l’espoir qu’un algorithme polynomial pour un problème NP complet nous donne un algorithme polynomial pour n’importe quel problème NP.

(Merci à mon ami Xoff qui m’a précisé tout ça !)

D’ailleurs, si vous voulez un exemple concret de transformation d’un problème, je vous recommande la vidéo de Passe-Science où il montre explicitement comment mettre en correspondance un problème SAT et un problème de coloriage de graphe avec 3 couleurs (autre problème NP-complet).

D’ailleurs sur le problème SAT, j’ai en fait présenté le problème parfois appelé CNF-SAT, où CNF veut dire « forme normale conjonctive ». En toute généralité, le problème SAT est celui qui concerne n’importe quelle formule. Dans sa version CNF, on se limite aux formules qui sont un « grand ET » de sous-expressions qui sont des OU. C’est de ça que j’ai tiré mon analogie de la sélection des membres du club : chaque membre représente un ensemble de OU, et on veut que chaque membre soit satisfait donc c’est un grand ET sur tous les membres.

Tiens détail amusant pour finir, que je n’ai pas réussi à caser dans la vidéo : 1-SAT et 2-SAT sont P, mais on peut définir 3-SAT qui est NP-complet. Je trouve ça assez remarquable de voir que 3-SAT (qui a l’air pourtant d’un problème plus réduit que CNF-SAT ou SAT, et à peine plus compliqué que 2-SAT) soit « déjà » NP-complet.

Edit du 18/07/2020 : Revenons sur le problème du sac-à-dos

Beaucoup de gens pensent avoir trouvé une solution au problème du sac-à-dos en triant les objets par « densité », c’est à dire « valeur en € par kg ». Ca donne une première idée, mais ça ne fonctionne pas.

Voici un exemple : un sac de 50 kg, et 3 objets. L’un de 36 kg valant 36 euros (densité 1), et deux de 25kg valant 20 euros (densité 0.8). Si l’objectif est d’atteindre 38 euros, il faut prendre les deux objets les moins denses.

Ce petit « contre-exemple » est très simple, mais montre que de façon générale, le fait d’utiliser la densité ne permet pas à coup sûr de conclure en temps polynomial. Surtout quand on commence à mettre des objets de densité proche de l’objectif.

48 réflexions sur “Est-ce que P = NP ?

  1. C’est drôle tous les problèmes qui m’intéresses tu les traites dans tes vidéos ! 🙂

    Et j’ai une piste pour celui-là ! C’est une énumération de tous les cas possibles, et du coup un classement (à découvrir) qui donne la solution à n’importe quel problème ! Je n’ai pas vérifié cette intuition, je suis tellement faignant (et surtout, aussi, tellement conscient que notre microscopique système solaire peut être pulvérisé à n’importe quel moment répartissant les molécules des oeuvres de Shakespeare, Einstein et tout le monde en « rien du tout »… Du coup pourquoi ne pas profiter plutôt tranquillement de la fantastique, et même incroyable vie qui s’offre à nous, privilégiés improbable (presque étonnant) dans l’univers 🙂 )

    Bon, pour ceux que ça intéresse, en détail, pour comprendre comment la solution s’organise, il faut énumérer toute les solutions possibles en fonction de toute les valeurs possibles et chercher un schéma. Il m’a semblé évident qu’il y en avait un quand j’ai regardé ça… Facile en plus… Mais je suis tellement faignant encore une fois que je suis bien content de vous donner ce résultat pour qu’il ne soit pas « perdu » au cas où ce soit pas trop mal comme idée.. 🙂

    Comme disait Omar Sharif (un de mes idole) : « ce qui n’est pas donné est perdu à jamais ».

      • Oui EK en effet c’est pas très clair comme explication de « l’intuition » je me rend compte en relisant 🙂

        Alors, déjà mon idée concerne le problème du sac qui est complet je crois, et avec un schéma ce sera mieux qu’avec mille mots comme on dit :

        On a des objets de diverses valeurs (1ere colonne) et de diverses masses (2 eme colonne) et on doit remplir un sac avec une limite de masse (énumérée sur la 4 eme ligne) en cherchant à obtenir la valeur maximum dans le sac. Dans le cas le plus simple celui du haut on a des masses et des valeurs égales et croissant en n^2 du coup on voit le schéma qui est clair bien sur, ça fait du binaire. Mais si on change les masses/valeurs en laissant les masses classées par ordre décroissant, celui du bas, on voit qu’il apparaît toujours une espèce de schéma qu’il est peut-être possible d’identifier donc, enfin j’ai l’impression, c’est « l’intuition » 🙂

        Voili voilou j’espère que c’est plus clair 😉

    • Je ne sais pas comment formuler ma question donc je vais prendre un exemple : dans le premier problème où il faut trouver un minimum dans une liste, les nombres de la liste semblent avoir été sélectionné au hasard… que se passe-t-il quand c’est un algorithme déterministe qui doit créer la liste ; quels sont les liens possibles entre l’algorithme générateur de la liste de nombre et l’algorithme solveur (qui doit trouver le plus petit nombre). Il semble évidant que si l’algorithme « générateur » consiste à générer une liste avec les 10 premières puissances de 2 (par exemple) alors le minimum de la liste sera 1 (le premier chiffre de la suite en l’occurence) mais de manière plus générale y a t-il un lien entre la complexité d’un algorithme « générateur » qui génère le problème et la complexité du « solveur » qui résous le problème (en supposant évidement que le « solveur » ait connaissance du code informatique du « générateur » qui a créé le problème).

      • Concrètement, c’est un autre problème.

        Plus exactement, lorsqu’on parle de complexité tout court, on pense à la complexité pire cas (worst case complexity). C’est à dire, pour une liste de longueur N quel est le temps maximal que va prendre mon algorithme, ou encore, quel est le temps que va prendre mon algorithme pour la « pire liste » de longueur N pour mon algo.
        Il peut effectivement arriver qu’en fait, ces pires cas ne nous intéressent pas parce qu’ils n’arrivent jamais, auquel cas on peut restreindre le problème à un sous-ensemble d’entrées très spécifiques. Ça peut être intéressant d’étudier ce nouveau problème, mais ce faisant on a changé le problème. Même s’il est similaire, ce n’est plus le même. Il ne s’agit plus de « trouver le minimum d’une liste » ou « trier une liste » mais de « trouver le minimum d’une liste vérifiant X condition » ou de « trier une liste vérifiant X condition ».

    • Désolé mais c’est du charabia. L’informatique théorique c’est une science, qui est bientôt centenaire, il serait bien de la respecter. Quel manque d’humilité de penser avoir une intuition que n’ont pas eu des milliers de chercheurs qui se sont cassé les dents sur ce problème. Surtout que c’est considéré comme un des problèmes les plus difficiles du monde.
      Pour l’anecdote en stage de L3 je bossais sur un truc qui avait pas grand chose à voir et j’avais prouvé un résultat (une vraie preuve hein, de plusieurs pages de maths velues, pas une « intuition ») dont une conséquence était que P=NP. Je me suis pas dit « wouah je suis un génie » j’ai cherché l’erreur dans ma preuve ce qui m’a bien pris une aprem.
      (Après je trouve ça très bien de s’intéresser aux choses quand on est pas specialiste attention ! Mais faut d’abord se frotter au problème, voir pourquoi il est compliqué, quelles solutions intuitives ont été tenté et n’ont pas marchés, etc…)

      • hola du calme la nouille, faut pas être si pressé de vomir son mépris, faut lire la suite, j’ai reconnu que j’avais pas été clair et plus bas et il y a une meilleure explication avec un schéma (ce qui était indispensable en fait bien sur).

        Après je ne suis pas du tout d’accord sur le fait qu’il faut « la fermer parce que c’est forcément nul ce qu’on dit tant qu’on a pas bac +12 et 20 ans de recherche en Math »… C’est justement ce qui attire les gens de bricoler des solutions, de chercher, de réfléchir ! Alors bien sur c’est pas toujours fantastique, mais au moins il y a des gens qui s’intéressent, qui débattent, qui progressent, doucement mais surement, et surtout ne vous en déplaise qui font des maths avec plaisir ! Et tant que ces gens se rendent compte que leur « idées » ont peu de chances d’être les découvertes du siècle je ne vois vraiment pas le mal.

        Quoi, vous avez peur que le « mont Olympe des maths » ne soit dévalorisé si des amateurs ose s’y aventurer en touriste ? Vous avez peur de perdre votre « grandeur », votre « importance de grand prêtre », qui vous a coûté tant d’année de travail en math pour monter là haut ? C’est ridicule, ayez plus confiance en vous, vous valez mieux que ça ! (sans doute).

        C’est justement s’il n’y avait que des gens comme vous que personne ne s’intéresserait plus au math et à la physique car tout le monde se dirait que ce n’est pas la peine, s’il faut faire 10 ans d’étude et 15 ans de recherche pour arriver au moindre résultat on serait tous découragés d’avance.

        Donc merci d’aller essayer de dissuader les gens de faire des maths ailleurs, sur votre forum habituel par exemple, ou vous êtes seul avec la même dizaine de « super expert » qui débattent ensemble depuis 20 ans en faisant la moitié du temps semblant de se comprendre tellement ce que dit chacun est compliqué et/ou faux (sans rien découvrir de plus que nous d’ailleurs) et merci de nous laisser nous amuser tranquillement ici !

        Non mais ! 🙂

      • Effectivement, Talep, il s’agit d’un des problèmes les plus impénétrable de nos jour.
        Je nuancerais toutefois ton propos par Deux idées :
        – D’une part, se frotter naïvement et prétentieusement à ce genre de problème permet souvent d’apprendre bien que de façon empirique, très fertilement obstacle par obstacle. Même si le problème n’est pas réglé au final, il n’en reste pas moins que l’aventure intellectuelle que constitue ce genre de réflexions est un grand plaisir.
        – D’autre part, l’histoire retient quelques outsiders porters d’intuitions improbable qui se sont avérées étonnamment clairvoyantes. Je pense en cela à Albert Einstein pour « l’invention » de l’espace temps en contradiction avec l’espace et le temps absolu de Newton. On peut également citer Roland Moreno qui à inventé la carte à puce que l’on utilise encore aujourd’hui (bien que bénéficiant de quelques améliorations ad’hoc).
        En résumé, émettre des intuitions me semble toujours une démarche intéressante. Une intuition pouvant en amener une autre, etc, etc.
        Mon idée est donc de ne pas se censurer sur le simple prétexte que nous n’exerçons pas le métier de théoricien de la science de haute volée. De nombreux vulgarisateurs comme David, donnent à beaucoup l’envie de réfléchir et utiliser leur cerveau, idée qui n’aurait peut-être jamais germée.
        Après une vulgarisation bien faite (comme cette dernière) où on a sincèrement la sensation d’avoir tout compris tant le propos est clair, ce que l’on apprend en premier est l’étendue de tout ce à quoi on ne comprend rien.
        Pour exemple, après avoir vue la vidéo sur « la gravité quantique à boucle », j’ai eu très envie de tout comprendre à ce sujet. Depuis, je gratte encore et s’il me semble que ma perception du sujet s’éclaircie, j’avoue avoir encore quelques problèmes sur la compréhension des raisons qui posent problèmes pour passer d’un espace temps à 2 dimension d’espace + 1 de temps à un espace temps à 3 dimension d’espace + 1 de temps.
        Il me semble tellement plus profitable de passer son temps à ce genre de tribulations qu’à regarder « les ange de la télé-réalité ».
        Pour conclure, soyons arrogants et visons les sujets les plus grandioses et délectons-nous de tous ce qui se trouve en chemin. Le voyage ne vaut-il pas autant que la destination ?

      • Talep ne cherche pas à « censurer » qui que ce soit, il pointe simplement que l’idée proposée ici est farfelue. Moi je pense qu’il vaut mieux s’en amuser, d’où ma remarque ironique rappelant l’anecdote de Fermat, et je pense que cela relève plus de l’ignorance que de la prétention (du moins j’aime à le penser). Ah, cet effet Dunning-Kruger… https://fr.wikipedia.org/wiki/Effet_Dunning-Kruger

      • Et voilà, c’est EK, assurément hautement diplômé pour avoir un avis aussi tranché et méprisant : « farfelu » ! Il rend cet avis bien engoncé dans son fauteuil, bien gros, bien dégoulinant de son plus beau mépris envers ceux qui prétendent parler d’un sujet dont lui-même n’a absolument aucune idée de par quel bout le prendre !

        Il ne nous donnera pas son idée à lui donc, n’y pensez pas une seconde, il n’a jamais eu d’idée, sur p=np ou quoi que ce soit, ni d’intuition même, c’est quelque chose qu’il ne connaît pas, qu’il n’a jamais ressenti… Non malgré tous ses diplômes, son prétendu « niveau », il n’a jamais rien trouvé, absolument rien, et même si au fond il en souffre un peu, il le sait, il l’a toujours su, il ne trouvera jamais rien. Jamais. C’est peut-être aussi pour ça qu’il n’a jamais tellement essayé.

        Mais c’est bon il n’y pense pas trop, et puis de brûler des amateurs qui se permettent d’oser prétendre avancer là où il patauge complètement, ça le rassure, il se sent mieux, c’est suffisant finalement. C’est amusant en plus, il peut les insulter, les traiter à demi-mot de crétins, de débile, grâce à l’effet Dunning-Kruger. Il rappelle l’anecdote de Fermat, ce qui en fait son complice tout à coup ! EK ! lui ! complice avec Fermat ! Il a les larmes aux yeux… Voilà, c’est fini, il va mieux.

      • Je ne sais pas pourquoi vous ressentez tant de haine. Je trouve cela super que des gens de toutes horizons, de toutes éducations, réfléchissent à toutes sortes de problèmes complexes. De nombreux commentaires ont humblement proposé une solution, en remarquant toutefois qu’ils pouvaient sans doute se tromper, n’ayant pas de connaissances dans ce domaine, et effectivement leur solution correspondait à l’algorithme dit « glouton », qui est loin d’être idiot (il faut déjà être malin pour penser à cet algorithme, mais ce n’est pas la proposition dont il était question ici) mais qui effectivement ne résout pas le problème (et qui est, par ailleurs, bien connu des chercheurs depuis bien longtemps). La « solution » proposée par notre ami ici n’est pas une solution, c’est un « charabia » comme le disait Talep, c’est des mots vides de sens, je suis désolé mais ce n’est pas « avancer une solution » que de dire « j’ai une intuition, je pense qu’on devrait pouvoir trouver une solution en réfléchissant (mais je ne réfléchirai pas par flemme) ». Talep trouvait cela extrêmement prétentieux, de penser qu’on est l’être élu, qui sans connaissance, a réussi là où nombre de chercheurs ont passé leur vie à réfléchir. Je comprends ce point de vue, mais je pointais du doigt que quelqu’un qui a très peu de connaissances dans le sujet manque sans doute de recul sur le problème et sur la recherche scientifique de manière générale, et donc n’est pas malveillante. Malgré tout, on peut s’intéresser à des sujets complexes sans avoir beaucoup de connaissances (c’est le but de la vulgarisation!), mais il serait de bon ton d’avoir une certaine honnêteté intellectuelle. Notamment, le genre de problème traité dans cette vidéo, ce ne sont pas les énigmes de Tante Huguette. C’est plutôt le genre de problèmes qui finissent par être résolu par un mathématicien qui aura travaillé pendant 40 ans dessus, en s’appuyant sur 200 ans de travaux d’autres grands esprits. Et qui aura eu une formidable intuition, mais une intuition basée sur ses connaissances, sur d’autres travaux, sur les 40 années passées à travailler… Et non sur une vidéo de vulgarisation (aussi bonne soit-elle) qui explique le problème de manière accessible à tous (super vidéo au passage, comme d’hab, mais vous comprenez bien qu’elle ne présente pas un état de l’art exhaustif de la recherche dans le domaine). Bien sûr que tout le monde a le droit d’y réfléchir de manière ludique et/ou formatrice, mais je pense qu’il faut avoir conscience de tout cela. Pour avoir très rapidement étudié ce domaine d’étude (qui n’est pas du tout ma spécialité), j’ai bien l’impression que la solution, si elle est trouvée un jour, reposera sur des arguments mathématiques assez complexes. Que dire de plus? Ne vous inquiétez pas pour ma carrière qui se porte très bien, et vous devriez relire l’anecdote de Fermat et de sa marge (car c’est tout sauf mon complice dans cette histoire). Et un minimum de respect envers les gens aide beaucoup quand on prétend effectuer un travail de recherche.

      • De la haine !? De moi pour vous ?! Non non 🙂 N’imaginez pas une seconde que je vous ferais cet honneur, vous rêver là 🙂

        Non vraiment, déjà je me suis bien marré en l’écrivant, et en plus je trouve ça drôle quand je le relis à chaque fois 😀 … C’est toujours un tel plaisir de rembarrer les gens pompeux et méprisant.

        Quand à ce que j’ai soit disant « donné » là, je l’ai donné avec sincérité, réelle, au cas ou ça vaudrait quoi que ce soit… C’est vrai je n’ai pas tellement envie d’y consacrer trop de temps, et aussi je ne l’ai pas précisé (à tort peut-être) mais il est très probable que je n’ai pas le niveau pour le faire donc pas la peine d’attaquer des châteaux imprenables c’est tout.

        Mais quand on voit l’accueil misérable on se rend compte que même donner quelque chose ça coûte assez cher, c’est « risqué » !… 😦 Quelle bêtise incroyable… Pourtant si ça ne vaut rien ce n’est pas grave, passons, quel est le problème ? Quel besoin d’en faire tout un cirque avec exécution publique, insulte et mépris !? Ca vous fait du bien ? Allez plutôt faire un footing, ça vous fera maigrir.

        Bon, allez, je vais relire mon commentaire précédent parce que là du coup j’ai besoin de me détendre un peu 🙂

      • Si le mot « farfelu » vous met dans cet état, il est sans doute préférable en effet de ne pas se lancer dans la recherche scientifique ; le processus de revue par les pairs est autrement plus critique que mon commentaire.

      • Fasafr, A quel moment ai je fais preuve d’une quelconque supériorité ? J’ai dit que c’était très bien de s’intéresser à des problèmes quand on est pas specialiste. J’ai juste pointé votre manque d’humilité a croire avoir trouvé une solution au problème et a « donner généreusement l’intuition pour le bienfait de l’humanité ».

        Je n’ai pas dit qu’il fallait la fermer bien au contraire. Juste aborder le problème avec du recul, plein de gens ici ont eu la même intuition de l’algorithme glouton et ne ce sont pas dit « ah cool j’ai résolu un problème du millénaire en réfléchissant dix minutes », ils se sont dit « hum doit un avoir une erreur même si je ne la vois pas ». C’est toute la différence.

        Je ne dissuade personne de faire des maths en touriste. Je fais moi même de la philo en touriste. Mais je suis jamais allé posté mon intuition sur le problème du trolley sur un forum de philo en disant « arrêtez de réfléchir, j’ai trouvé ! ». Je trouve que ce serait dévaloriser la philosophie et les philosophes, comme je trouve que penser avoir une solution pour P=NP c’est dévaloriser l’informatique théorique.

        Pour le fond c’est triste a dire mais oui les sciences sont devenues tellement spécialisées que oui il faut dix ans d’étude pour arriver à trouver un résultat nouveau. Et encore ce sera un résultat mineur qui ne prendra son sens qu’au sein d’une myriade d’autres résultats. C’est d’ailleurs a mon sens un problème.

        @Marc je suis tout à fait d’accord avec le premier point, c’est en bricolant qu’on comprend. Le deuxième me paraît plus disputable (surtout pour enstein car d’une la science a l’époque était moins « spécialisée » et de deux car ce n’était pas non plus le premier venu et il a mis du temps à produire ses travaux et surtout à convaincre la communauté scientifique de leur validité). Enfin vous semblez être d’accord avec moi, car mon message initial critiquant le manque d’humilité de l’auteur, se prendre pour enstein n’est ce pas là le comble de l’arrogance ? 😉

        @EK J’ai personnellement beaucoup apprécié le commentaire sur la marge trop petite ^^

        @Fab Expliquez moi en quoi pointer du doigt le fait que c’est un problème extrêmement compliqué, qui a résisté à des générations de chercheurs plus brillants les uns que les autres c’est du mépris, mais que penser avoir une intuition, être trop fainéant pour la pousser plus loin, mais la donner pour faire profiter les autres de son génie (le tout sans prendre la peine d’utiliser un vocabulaire mathématique un minimum rigoureux) n’en est pas ?

  2. Notons que la borne inférieure en $O(n \log n)$ pour la complexité d’un tri n’est valable que pour les tris basés sur les comparaisons.
    On peut, avec des hypothèses sur les données à trier, obtenir de meilleurs algorithmes, comme l’algorithme de tri comptage de complexité linéaire.

  3. Super vidéo! Ca colle un peu mieux avec ce que je fais dans mes études et mon boulot vu que c’est en lien avec l’informatique. Je me rend compte à quel point tu vulgarises bien en utilisant pleins de petites « passerelles » pour capter l’attention.
    Par exemple le million de dollar, le fait que ça permetterait théoriquement de craquer les chiffrements RSA, etc…

    Bref continue ce que tu fais tu n’est pas ma chaine youtube préféré pour rien 🙂

  4. Bonjour,
    J’ai, il me semble, un algorithme P pour le problème du sac à dos. Ceci dit, ça serait surprenant que je sois le premier à y avoir pensé ^^. Comment dois-je opérer pour soumettre ma solution?

  5. J’ai trouvé une solution beaucoup plus simple est évident pour le problème du sac a dos, et vu mes compétence en math je pense qu’elle devrai avoir une valeur entre 2N et 3N, mais ne suis pas capable d’être plus précis a moi tout seul.
    Si vous avez l’occasion de me contacter sur mon e-mail n’hésitez pas.

    • Au risque de te décevoir, il y a d’énormes chances pour que ta solution soit incorrecte. C’est notamment assez commun d’oublier une subtilité d’un problème NP-complet et d’avoir une solution qui marche décemment dans les cas qui nous semblent raisonnables, mais en fait se casse la figure dans ceux auxquels on avait pas pensé parce que le problème est plus général que ce à quoi on pense.
      Mine de rien, ça fait un bout de temps que la question a été posée (plusieurs décennies) et que des chercheurs ont buté dessus sans succès. Ce n’est pas impossible que quelqu’un trouve une solution simple par hasard, mais c’est quand même extrêmement improbable. Les chercheurs de métier aiment bien les solutions simples aussi, et ils sont plutôt doués pour les trouver.
      Néanmoins, n’hésite pas à poster une ébauche de solution si tu veux qu’on examine ton raisonnement (enfin, ce n’est pas mon blog, mais personnellement ça ne me dérangerait pas de jeter un œil, histoire de voir où est l’erreur parce que je suis sûr à 99.9999% qu’il y en a une). Le cas échéant, si tu as peur qu’on te vole ta solution, je te suggère d’essayer d’écrire un sat solver sommaire l’utilisant (quitte à écrire une réduction de sat vers knapsack), a priori, le problème devrait apparaître assez vite (et s’il n’y en a pas… eh bien, tu auras peut-être quelque chose d’exploitable ?).

      • Je m’en doute, et même si j’aimerai bien avoir raison, je pense aussi qu’il y a de bonnes chances que mon niveau académique ne me permette pas de voir une étape du processus de résolution.
        Toutefois, j’ai déjà eu l’occasion de voir une solution à un problème plus complexe, dans une entreprise de 4 millions d’employé, et à laquelle encore personne n’avait pensé.
        Donc on sait jamais, peut être que des concepts évident pour moi sont plus abstrait pour d’autres.
        Et si je me trompe tant pis, ce sera une occasion d’apprendre d’où vient mon erreur et d’approfondir mes connaissances.

  6. Maintenant je suis prêt à partager à 50/50 toute récompense éventuelle avec la personne qui ferait les maths pour mon idée, en laissant la priorité à sciences étonnante, qui mériterai bien un cadeau pour son excellent boulot.
    Et oui je suis fan.

    • T’es un tel bullshitteur imbue de ta personne c’est incroyable. L’entreprise avec le plus d’employés au monde est Walmart avec 2 millions 300 000. J’ai toutes les compétences qu’il faut pour écrire ta solution (bien plus que science étonnante en fait, il fait un formidable travail de vulgarisation, mais c’est un physicien, pas un mathematicien ou un computer scientist. Encore une fois l’informatique théorique c’est une vraie science bordel) et j’ai tellement envie de te mettre le nez dans ton caca que je te laisse 100% des gains, plus mon bras gauche si ta réponse marche. (Oui je suis pas comme olxinos je suis moins sympa et j’ai pas besoin de prendre des précautions avec des 99,9999% je suis sur à 100% qu’il y a une erreur)

      • L’entreprise dont je parle c’est Amazon, donc déjà la ferme, ensuite l’idée que j’ai eu ne vaut rien vu que c’est juste la formule du glouton.
        Sinon arrête de penser avoir raison parce que tu as un meilleur niveau d’étude.
        Et franchement même si il est moins compétent dans le domaine, comme tu l’a dit science étonnante fait un super boulot et sans lui j’aurais pas eu cette idée donc partager la prime avec lui aurai été naturel.
        Maintenant la prochaine fois réfléchi avant d’agresser les gens.

      • Je ne me crois pas supérieur par rapport a mon niveau d’étude. Par contre oui, le fait d’avoir bossé dix ans là dedans fait que je sais un peu de quoi je parle. Je considère en plus que trouver l’algorithme glouton quand on est pas specialiste c’est très bien. Ça montre un intérêt pour le problème, de bonnes idées, une envie de bricoler une réponse, etc… Mais plein de gens dans les commentaires l’ont fait en disant « mais bon y’a peu de chances que j’ai résolu le problème du millénaire en cinq minutes » pas en disant « il est possible que ce problème du millénaire me soit totalement intuitif et que des générations de chercheurs soient de gros tocards ». Désolé de trouver que ce discours rabaisse une science qui est déjà pas très mise en valeur.

        PS : Amazon d’après une recherche rapide sur Internet compte 500 000 employés.

  7. Bonjour,
    Une solution simple au pb du sac a dos que j’ai posté en commentaire sur Youtube serait
    1/ attribuer une densité (euros / kg ici) a chaque objet (cardinalité N) ;
    2/ faire un tri rapide de la liste par ordre décroissant de densité (cardinalite N × log (N)) ;
    3/ parcourir la liste triée par ordre de densité décroissante et mettre dans le sac à dos les objets lorsqu’ils peuvent rentrer dans la place encore restante (cardinalité N) ;
    4/ vérifier la solution pour conclure (cardinalité N).
    Du coup le problème du sac a dos (tel que formulé ici hein 🙃) admet un algorithme de cardinalité N × (k + log (N)) avec k = 4… bref c’est un algorithme P, non ?
    Par contre je ne peut pas démontrer que c’est l’algorithme qui ramène « la » meilleure combinaison.
    A vous lire et encore merci David pour tes vidéos toujours passionnantes et très bien faites.
    Michel

    • Bonjour Michel,
      Je pense que nous avons eu la même idée. Ce à quoi Olivier m’a aiguillé vers https://fr.wikipedia.org/wiki/Temps_de_calcul_pseudo-polynomial.
      L’algorithme que vous décrivez est déjà connu et à pour nom « glouton ».
      Selon moi, cet algorithme est une optimisation en poids embarqué mais je ne sais pour quelle raison la communauté mathématique ne s’en est pas satisfaite. Je ne la savais pas à ce point capitaliste ;).
      Peut être devriez vous éprouver votre solution sur l’énoncé du lien hypertexte et voir si votre algorithme renvoie les 12$ pour 14kg.

      • je prend le problème à l’envers : pas compliqué de construire un jeu de données qui conduit l’algorithme a ne pas proposer la solution optimale. donc pas la solution (trop simple ;-D)

      • en fait le problème consiste soit à déterminer un index de classement qui permet de collecter les objets dans un ordre qui sera toujours optimal… soit démontrer que l’algorithme pour l’élaboration d’un tel index de classement est nécessairement NP

  8. Pour le problème du sac à dos j’ai eu l’idée d’un solution ( je me doute qu’il doit y avoir un problème puisque c’est un problème NP mais j’arrive pas à le trouver) : raisonner en Prix / Masse. Cela permet d’être sûr qu’on prends l’objet les plus « rentables » en premiers.
    il suffit de faire ce calcul pour chaque objet DensitéPixMasse = Prix / Masse , puis de trier les objets selon ce nombre, puis enfin de garder uniquement ceux ayant le meilleur DensitéPixMasse jusqu’à ce que les 5000$ soient atteint. Si ils ne sont pas atteint avant que la masse totale des objets choisis dépasse 50kg alors le il n’est pas possible de résoudre le problème avec les objets donnés.
    L’algorithme est bien en temps polynomial, toutes les opérations utilisées le sont !
    Bon ça marche si il y a un nombre maximum d’objet, ou autre, mais tel que le problème est posé je n’arrive pas à trouver le problème avec cet algorithme.
    Si quelqu’un a une idée j’aimerais bien savoir…

  9. Après avoir lu plus en détail l’article Wikipedia, je comprends maintenant pourquoi l’algorithme dit « glouton » n’est pas satisfaisant. L’énoncé du problème est : Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum. Dans la vidéo, le problème est amené différemment d’où la confusion ^^. Monde capitaliste de m€#@3 :). Très bonne vidéo ceci dit.

    • C’est bien la façon dont le problème est amené dans la vidéo qui est la « bonne ».
      La formulation du problème du sac à dos qui est NP-complète est celle où on cherche à placer des objets dans le sac de façon à avoir *au moins* une valeur fixée.
      On ne cherche pas à avoir le *maximum* de la valeur (ce problème est beaucoup plus compliqué : ne serait-ce que pour *vérifier* que la solution est optimale il faudrait déjà savoir le résoudre, autrement dit il n’est même pas sûr qu’il soit de classe NP)
      (La formulation utilisée dans la vidéo est bien donnée dans Wikipedia mais un peu plus bas : https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos#NP-compl%C3%A9tude)

      Le problème avec l’algorithme glouton, ce n’est pas qu’il donne une solution non-optimale : c’est qu’il ne donne tout simplement pas de solution dans le cas général : un objet dense en valeur peut, si il est trop lourd, empêcher de prendre des objets moins denses en valeur mais qui ensemble permettraient d’atteindre la valeur limite fixée.

      Pour être sûr que ça n’arrive pas, il faudrait recommencer l’algorithme en enlevant le dernier objet le plus dense ajouté, de façon récursive, en suivant un arbre, ce qui au final se ramène à tous les autres algorithmes simples qui sont de complexité exponentielle.

  10. Bonjour,
    je ne sais pas si ça vous intéressera, mais voici une formule mathématique qui tente de démontrer qu’il n’y a pas de possibilité (en fait, une seule, mais pas transposable) pour qu’une société monétaire soit « juste », « équitable », bref, sereine.
    si ça vous dit… http://www.la-formule.xyz

  11. Concernant la Primalité d’un nombre N, si vous souhaitez découvrir un algorithme de complexité LINEAIRE (mieux que l’AKS … !), vous pouvez consulter l’adresse suivante : http://villemin.gerard.free.fr/Wwwgvmm/Compter/Factprim.htm ou directement l’adresse : https://www.youtube.com/watch?v=2y0m0EllJRg
    Par exemple pour savoir si 857 est premier, il ne vous faudra que 429 itérations.
    Cet algorithme utilise les super-primorielles au fur et à mesure du calcul des nombres premiers inférieur à N. ATTENTION : POUR FONCTIONNER, L’ALGORITHME DOIT ETRE ECRIT AVEC UN LANGAGE CAPABLE DE MANIPULER DES GRANDS NOMBRES, AU-DELA DE 10 PUISSANCE 16. (PYTHON PAR EXEMPLE).

  12. Concernant la Primalité d’un nombre N, si vous souhaitez découvrir un algorithme de complexité LINEAIRE (mieux que l’AKS … !), vous pouvez consulter l’adresse suivante : http://villemin.gerard.free.fr/Wwwgvmm/Compter/Factprim.htm ou directement l’adresse : https://www.youtube.com/watch?v=2y0m0EllJRg
    Par exemple pour savoir si 857 est premier, il ne vous faudra que 429 itérations.
    Cet algorithme utilise les super-primorielles au fur et à mesure du calcul des nombres premiers inférieur à N. ATTENTION : POUR FONCTIONNER, L’ALGORITHME DOIT ETRE ECRIT AVEC UN LANGAGE CAPABLE DE MANIPULER DES GRANDS NOMBRES, AU-DELA DE 10 PUISSANCE 16. (PYTHON PAR EXEMPLE).

    • Le problème, c’est que l’opération modulo à l’intérieur de votre boucle a elle-même une complexité linéaire. Donc au final, votre algorithme a une complexité quadratique (bien pire que le crible d’Ératosthène… !)

  13. Bonjour,
    ce passage n’est pas correct dans le début du commentaire désirant préciser la video « Comme je l’ai dit dans la vidéo, il est tentant de penser que NP signifie « non-polynomial ». Mais il s’agit en fait de la classe des problèmes de décision « vérifiables » en temps polynomial. Evidemment, cette « vérifiabilité » ne concerne que les cas où la réponse est « oui ».

    (Pour les gourmands, on peut définir la classe co-NP qui est en gros la même chose, mais en symétrique : vérifiable en temps polynomial quand la réponse est non. D’ailleurs on ne sait pas si co-NP = P et/ou co-NP=NP). »

    Voir par exemple : https://fr.wikipedia.org/wiki/Co-NP pour une définiton accessible sur le web sans passer par les écrits spécialisés. La confusion vient du fait que beaucoup pensent que NP = vérifiable en temps polynomial signifie exclusivement vérifier en temps polynomial qu’une solution potentielle du problème est une solution. En fait il faut parler des certificats ou témoins, et un potentiel témoin (indice) que le problème a une solution peut être un autre élément (mot) que la solution : https://fr.wikipedia.org/wiki/NP_(complexit%C3%A9)

  14. Bizarre, Le problème des étudiants admis est vraiment un NP COMPLET ? Car peu importe le nombre de votants ou d’étudiants car seul compte les votes. Et c’est au final un tri pondéré qui ne garde que les numéros dont le résultat de la somme des votes positifs et négatifs est >0. Ce tri appartient à N. La limite basse est aucun étudiant admis, la limite haute tous les étudiants admis.

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s