Bonjour Monsieur Passe-Science, en tant qu'informaticien je peux donner un avis éclairé sur cette vidéo de vulgarisation : elle est vraiment excellente ! Il me semble que pour présenter cette question complexe au grand public en seulement douze minutes, on ne pourrait pas vraiment faire mieux.
d'ailleurs, en informatique, c'est pour cela qu'on développe les réseaux neuronaux a plein tube... le but etant qu'il vaux mieux avoir une reponse rapidement que la reponse la plus optimisé possible... (l'un n'excluant pas l'autre)... en gros : pour cela, on colorie au hasard les noeuds... la ou ca marche on donne des points selon le resultat... puis on recommence... si par exemple le point A a recu beaucoup de point quand il etait bleu on aura tendance a le colorier bleu (toujours au hasard donc)... etc... on peux aussi au bout d'un moment cree une sorte d'ADN regissant les relations entre les noeuds puis de le faire evolué de maniere plus """formel"""...
Justement, un "avis éclairé" c'est quelqu'un qui n'y connais rien et qui, à la fin de vidéo peut déclarer ou non "j'ai tout compris !" et non pas quelqu'un "du milieu". Vous avez donc un degré quasi nul de légitimité pour juger de la qualité de vulgarisation de cette vidéo.
excellente vidéo j'ai adoré tes exemples concret... sa serait cool si tu pouvais mettre a notre portée les 6 autres problèmes mathématique du millénaire ! du très bon boulot comme d'hab un GRAND merci
Tellement riche et intéressant quelle dommage que les mathématiques ne soit pas plus mis en avant l'importance de cette discipline est pourtant capitale !
Super vidéo (comme d'habitude), Merci beaucoup ! Je suis ingénieur bac+5 en Maths appliqué et je suis admiratif de la qualité de vos vulgarisations qui contrairement à beaucoup d'autres rendent bien compte de l'essence du problème sans rentrer entièrement dans les détails mais sans le dénaturer non plus et sans dire de choses fausses et introduire des représentations mentales erronées, ce qui montre votre maitrise de ses sujets (je peux en tout cas le certifier pour vos vidéos sur les maths (Ex : groupe de gallois)). Vous m'avez vraiment débloqué sur certains points en physique (notamment le spin), merci. J'ai une question/conseil cela dit. Je ne comprends pas comment vous trouvez le courage de répondre à certains commentaires arrogants au possible où on sent dès le premier message qu'ils ne comprennent pas le sujet et qu'ils sont très probablement fermés à la discussion car ils n'ont pas envie de faire l'effort de comprendre (et n'ont d'ailleurs souvent même pas le niveau de comprendre pourquoi ils disent n'importe quoi). Vous écrivez parfois de longues réponses à ces personnes qui ne veulent pas reconnaître leurs torts alors qu'elles n'y connaissent rien et se sont à peine renseignées sur le sujet... Je l'ai vu plusieurs fois et le summum arrive sur cette vidéo (c'est aussi pour cela que je vous écris) où vous répondez des pavés à un collégien hautain et dé***. Comment avez-vous cette patience ? Mon conseil si vous me le permettez : Ne perdez pas votre temps avec ces personnes-la !! Elles vont grandir/comprendre d'elles même plus tard si elles s'y intéressent vraiment. De plus, presque-surement, vos réponses ne serviront à rien et leurs réponses à eux risquent de vous frustrer. Identifiez-les (avec votre niveau de compétence, ça se détecte très vite) et ne perdez pas de temps à répondre ou en tout cas ne rentrez surtout pas dans le "débat". A la limite, si vous êtes courageux (ce qui me semble le cas ^^), expliquez dès votre 1ère réponse brièvement pourquoi ils ont tort, renseignez éventuellement les points clés à aller rechercher (pour permettre à d'autres personnes plus humbles et se posant les mêmes questions de trouver les réponses) puis oubliez-les ! Et encore merci pour la qualité de vos vidéos (un cran au dessus de beaucoup de vulgarisateur de cette plateforme) ! PS : D'ailleurs à titre personnel et purement subjectif : Etes-vous plus pro- P = NP (vous pensez que c'est vrai et qu'on arrivera à le démontrer un jour) ou pro P différent de NP ou encore que cette proposition est indécidable (dans ZFC) ?
Hello! Sur P vs NP, j'imagine que la réponse doit être P différent de NP avec une démo pas très complexe, juste pas évidente à trouver (la réalité est souvent décevante) mais je préférerais que P=NP avec une démo bizarre ça serait très intéressant. Il y a beaucoup d'exemples en maths ou des comportements réguliers finissent par se briser, ca serait rigolo qu'on puisse résoudre n'importe quel pb NP complet en hardcodant juste 16 milliards de réponses et que la suite soit régulière et se ramène toujours à un de ces cas. Oui je répond à beaucoup de gens mais ne vous inquiétez pas je ne suis pas naïf, je le fais: par disponibilité (j'ai pas masse de commentaire, en moyenne horaire moins de 1 par jour), par ennuie ou pour éviter de faire d'autre chose que je dois faire (une esquive psychologique qui me permet de tourner autour du pot), pour le public (il y a des gens qui passent par la et lisent les réponses), parfois juste parce que j'aime tenter de trouver les mots justes, parfois par curiosité sur la nature humaine et je me place à un niveau méta pour observer comment les gens réfléchissent argumentent et changent d'avis ou non (avec la personne dont vous parlez par exemple j'ai découvert me tromper complètement sur ses limites, en tout cas mal les évaluer, meme si c'est ultra naïf il a quand meme réussi à pondre un truc sur le pb des 3 couleurs qui à résolu mes 4 premiers tests de graphes, ca reprend la formule d'Audiard "un intellectuel assis va moins loin qu'un con qui marche", faut pas sous évaluer), et aussi dans une démarche sceptique pour voir si ma posture à autant de fondement que je ne pense (notamment dans les débats sous la vidéo sur l'évolution) et je suis toujours surpris de découvrir que ces fondements sont épistémologiquement bien moindre que je n'imagine, surtout lorsque le même jour je démonte une théorie fumée et que je répond à un mec qui "démonte" l'évolution, car ca me place des deux côtés et je peux remarquer d'énormes similitudes de méthodes qui ne devraient pas être la si ma démarche était aussi rationnelle que je pense. C'est un point qui demanderait des exemples mais ya un mec qui parle pas anglais qui me reprochait de lui demander de parler anglais pour avoir accès aux "preuves en faveur de l'évolution" et d'un autre côté je ne vais surtout pas aller apprendre l'arabe pour prendre connaissance des arguments du coran en faveur de l'existence de dieu. De prime abord on peut se dire que ca n'a rien à voir, mais en y réfléchissant on peut s'interroger sur les fondements de cette déclaration, pourquoi je trouve légitime à quelqu'un qui critique l'évolution de lui demander de prendre connaissance des arguments pour dans un langage (à la fois étranger dans la langue et étranger en technicité) qu'il ne maîtrise pas et que je trouve en même temps ma position à ne prendre connaissance de rien sur le coran tout aussi légitime. On va tenter de se répondre en disant "oui mais de mon coté c'est le consensus scientifique" mais est ce une bonne justification de croire juste comme le consensus? lui aussi crois en un consensus (juste d'une autre nature) etc... Ca confronte à un relativisme épistémique parfois aliénant. Ne vous inquiétez pas je ne remet pas vraiment en cause les conclusions, ca me permet de faire une introspection épistémique comme je le montre avec cet exemple pour illustrer une des raisons pour lesquelles je réponds, et on est très très surpris souvent lorsqu'on se prête à l'exercice. Du coup à terme on raisonne mieux et on a de meilleures curseurs de credence.
Vraiment de l'excellent travail ! C'est toujours hard tes videos mais c'est pour ça que je te suis. J'ai vraiment l'impression d'apprendre des trucs et pas de simplement survoler très legerement un sujet (choses rares pour les chaines youtube science)
Excellent, ce sont des notions très abstraites et très verbeuses et tu les rends beaucoup plus abordables. C'est la première vidéo que je vois sur cette chaîne et je vais aller explorer les autres !
Merci beaucoup pour les encouragements. Sur des thèmes proches de celle ci il y a notamment l'axiomatisation, l'incomplétude, la machine de Turing, et biensur tous les autres thèmes j’espère peuvent aussi t’intéresser.
Bonjour, merci pour cette vidéo très claire. Je ne connaissais pas cette problématique avant la lecture du roman "Une machine comme moi" de Ian McEwan qui ne parle pas de ce sujet en profondeur mais qui l'évoque. Le roman parle d'un homme qui achète un robot qui a une apparence humaine et une forme d'intelligence très évoluée. Le narrateur rencontre Alan Turing qui, dans une version de l'histoire différente de la notre, n'est pas mort. J'ai lu des explications sur P vs NP sur Internet, mais aucune n'était aussi claire pour moi (qui ne suis pas mathématicien) que cette vidéo
Bravo pour cette vidéo de vulgarisation très bien réalisée! Je suis étudiant en informatique et elle m'a beaucoup aidé dans mon cours de calculabilité. Continuez, moi j'adore!
De rien. Je sais que c'est toujours agréable d'avoir un commentaire encourageant, surtout quand on le mérite! Ce problème p=np m'a toujours intéressé et intrigué.
Chaine génial ! En tant qu'étudiant en 3 ème année de mathématiques grâce à vos explication et aux images que vous donnez , j'ai l'impression de mieux comprendre certain thème déjà abordé en cours ( Théorie des Ensembles, exct ... ). Continuez c'est vraiment très bien et très travaillé à mes yeux. Ps: Es-ce possible de faire des vidéos sur les différents problèmes de Hilbert ou autres , car je trouve que voir les problèmes mathématiques récemment posé pour faire avancé les sciences sont très intéressant et de très bon thème a exploiter.
Non mais il est possible que l'on ne sache jamais si P=NP car certaines affirmations ne sont pas prouvable si falsifiables. P=NP pourrait être l'une de ces affirmations.
Bonjour ! J’ai du mal à me représenter la chose, est-ce qu’il est possible de transformer une grille de sudoku en un graphe à 3 couleurs ? En tout cas, la vidéo a rendu le problème bien plus clair pour moi qui suis un piètre mathématicien. Merci beaucoup :)
Hello, Oui on pourrait totalement transformer rapidement un sudoku quelconque en un problème de 3-coloriage, tel qu'une solution de ce dernier nous donne une solution du sudoku. On peut s'en rendre compte simplement (mais pas du tout de manière minimale) en utilisant l'exemple de la vidéo: on pourrait coder la valeur de chaque couleur de chaque case d'un sudoku sur plusieurs bits, et l'ensemble des contraintes sous la forme d'une grosse formule binaire à satisfaire (peut être énorme) et la vidéo montre ensuite comment représenter n'importe quelle formule binaire en 3-coloriage. Mais c'est juste pour se convaincre que c'est possible, y a certainement plus efficace pour reformuler un sudoku en 3-coloriage que de passer par des centaines de variables binaires :) *Précision:* en général quand on s'intéresse à la transformation de problème c'est dans le cadre d'une question de complexité algorithmique pour les résoudre, on s'intéresse au nombre d'opérations élémentaires à faire en fonction de la taille de l'énoncé. Si le problème est un 3-coloriage on voit que cette notion de taille est triviale, c'est par exemple le nombre de nœuds du graphe auquel on s'intéresse dans la famille infinie des graphes pour lesquels on pourrait se poser cette question. Il peut y avoir des graphes de toutes les tailles, notamment des graphes aussi gros qu'on le désire et donc cette question de complexité prend un sens, puisqu'on peut du coup regarder comment évolue le nombre d'opérations d'un certain algorithme en fonction de la taille de notre énoncé. Si je dis ceci c'est parce que les "sudoku" ne sont pas une famille infinie d'énoncés, et qu'on a pas de notion de taille arbitrairement grande dans un sudoku, ils ont tous la même taille. Du coup se poser des questions de complexité algorithmique n'a pas de sens. Cependant on peut considérer que les sudokus sont une sous-famille d'un truc plus général: un problème de satisfaction de contraintes, similaire à un 3-coloriages, mais avec 9 couleurs, et des zones ou les couleurs similaires sont interdites plus complexes que simplement les voisins. Dans une telle famille généralisée on pourrait du coup se poser la question de la complexité algorithmique, et comme c'est clairement un type de problème ou vérifier la validité d'une solution se fait rapidement, (temps polynomial) alors c'est par définition dans la classe NP, et comme le problème de 3 coloriage est NP-complet, alors par définition on peut transformer toutes les instances de notre famille NP de problèmes en des instances de 3 coloriages équivalentes (et le faire rapidement en temps polynomiale)
@@resolution-de-probleme Eh bien ceci ca vient de la propriété des problèmes NPC: comme vous pouvez transformer n'importe quel problème NP en une version du problème NPC de votre choix et le faire en temps polynomial, alors forcément il suffit d'en résoudre un seul NPC en temps poly pour démontrer que P=NP puisqu'ensuite vous pourriez prendre n'importe quel problème NP, commencer par le convertir en temps poly dans le problème NPC pour lequel vous avez une solution poly puis utiliser cette solution poly. Si vous demandez comment on démontre qu'il y a des problèmes NPC (c'est à dire des problèmes dans lesquels on peut transformer en temps poly n'importe quel autre NP en eux) il suffit de démontrer cette propriété pour un problème particulier, le problème SAT, c'est la theoreme de Cook: fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Cook Dans un second temps si vous voulez démontrer la NP complétude d'autres problèmes que SAT il suffit de montrer qu'on peut transformer SAT en eux comme je le fais dans la vidéo en transformant SAT en un problème de 3-coloriage (ce qui montre donc que tout problème peut aussi s'exprimer en probleme de 3-coloriage puisque d'après Cook tout problème NP peut s'exprimer en SAT, on en deduit du coup que le 3 coloriage est aussi NPC)
Belle vidéo, j'ai dû écouter une deuxième fois la réduction SAT → 3-coloriage pour comprendre, mais c'est clair et bien présenté :) Mais voilà des décennies que des gens très brilliants essaient sans succès de démontrer que P ≠ NP ou que P = NP (je viens de voir sur wikipédia que c'est peut-être indécidable aussi), alors il est très peu probable que je puisse y arriver même avec beaucoup de soirées pluvieuses à disposition (＾▽＾)
En fait faut se méfier de cela, par exemple une possibilité simple pour qu'un "lambda" comme nous prouve ce genre de chose, ça serait que P=NP et que sur un des problèmes NP complet connus on trouve juste un algorithme rapide auquel on aurait pas pensé. Apres si P ≠ NP il peut y avoir des arguments diagonaux et courts qu'il faut juste trouver, et ça tout le monde peut le faire, sisi, après si la seule démonstration possible est une démonstration technique de 30 pages, oui ça ne sera jamais à notre portée. :) "Beaucoup de gens ont essayé" je dis toujours que lorsqu'on dit cela, on compte toujours dans la statistique le beaucoup de gens qui étaient comme nous, du coup il faut tenter nous aussi ! parce que si on trouve normal de les comptabiliser, on doit trouver normal de s'inclure dans le processus de recherche, au pire on risquerait de trouver!
Et si je ne me trompe pas, il y a une sous-catégorie dans la catégorie NP-complet, ce sont les problèmes quantum-resistant car certains peuvent être résolus par un ordinateur quantique en temps polynomial. Je me demande si cette classification est bien claire, quels sont les problèmes qui sont quantum-resistants et lequels ne le sont pas. J'en connais quelques un dans ces 2 catégorie en cryptographie mais je n'ai pas une vue au-delà ... j'aimerais savoir.
Bonjour, Merci pour la video, tres interressant! J'ai une petite question minute 10:02. Pourquoi si NP-complet = P => NP-complet = P = NP ? Merci Christophe
Hello. Par définition P est inclus dans NP, et NP-complet est une sous partie de NP avec une certaine propriété: ce sont les problèmes à qui on peut ramener en temps polynomial n'importe quel problème NP. Ce n'est pas du tout évident que cette propriété existe c'est juste un fait mathématique: il y a une famille de problèmes à qui on peut ramener n'importe quel problème de la classe NP en temps polynomial et on appelle ces problèmes NP-complet). RQ: comme n'importe quel pb NP-complet est aussi un problème NP par définition ils sont aussi équivalents entre eux: c'est à dire qu'on peut passer d'un problème NP-complet à un autre de notre choix en temps polynomiale. Ainsi si le moindre problème NP-complet peut être résolu en temps polynomial alors, n'importe quel autre problème NP pourrait être résolu en temps polynomial (puisque par définition on pourrait dans un premier temps se ramener à celui qu'on sait résoudre rapidement). Et si n'importe quel NP peut se résoudre en temps poly alors par définition NP inclus dans P. Si NP inclus dans P alors que P inclus dans NP et bien les deux classes sont un seul et même ensemble. Il y a un des points qui n'est pas clair?
Hello, Merci beaucoups pour la reponse, je pense avoir compris la nuance dans la definition de NP-complet ("il y a une famille de problèmes à qui on peut ramener n'importe quel problème de la classe NP en temps polynomial et on appelle ces problèmes NP-complet"). Je pensais avoir compris que les problèmes NP-complet étaient uniquement une classe de problèmes simplifiables . Mais, si J'ai bien compris, les problèmes NP-complet sont en fait des problèmes qui permettraient de résoudre aussi les problèmes de classe NP en temps polynomial. D'ou NP-complet = P => NP = P J'espere avoir bien compris :) Encore merci pour vos videos!!
Bonjour, merci pour votre vidéo, elle est très pédagogique et je l'ai montrée à mes élèves. L'un d'entre eux m'a fait remarqué à raison qu'il y a une petite erreur autour de la 10ème minute quand vous dite qu'il se peut que NP_Complet=NP=P. En effet, on aura toujours NP_Complet strictement inclus dans NP (tous les problèmes NP ne sont pas NP_Complets...)
Hello, merci pour les compliments! pour le reste je maintiens ma version :p, le diagramme que je montre est similaire à celui de Wikipedia ici: en.wikipedia.org/wiki/P_versus_NP_problem#/media/File:P_np_np-complete_np-hard.svg issu de cette page: en.wikipedia.org/wiki/P_versus_NP_problem dans lequel on voit que dans l'hypothèse ou on aurait un exemple de NP-complet dans P alors P=NP=NP-complet. Mais je pense que je comprends votre étonnement, car initialement on sait que: P inclus dans NP, et NP-complet inclus dans NP. Si on exhibe un élément de NP-complet qui soit dans P alors instantanément on a une autre inclusion: NP inclus dans P. Ce qui amène à un diagramme ou on a un gros ensemble P=NP et dedans un ensemble potentiellement plus petit comme vous dites, les NP-complets. Alors pourquoi Wikipedia et mon diagramme montre aussi l'égalité NP = NP-complet dans ce cas ou P=NP? he bien je pense que ça vient des définitions rigoureuses de ces classes: un problème sera dit NP-complet lorsqu'on peut réduire en lui n'importe quel problème X en temps polynomial, et je crois me souvenir que ça se décrit plus précisément en terme de machine de Turing et de sous routine (on s'autorise le droit d'appeler le solveur du problème NP-complet). Cependant lorsqu'on a NP=P cette "réduction en temps polynomiale" devient un peu pathologique, car étant donné un problème K dans NP quelconque et un autre problème X dans NP lui aussi quelconque on peut utiliser le solveur de K pour résoudre X de la manière dégénérée suivante: On résout X en temps polynomial. On appelle le solveur de K pour ne rien faire. et on a donc au final la solution de X. Et K est donc "NP-complet" dans la mesure ou en connaître un algorithme de résolution polynomial permet d'avoir un algorithme polynomial pour X. Donc je crois que c'est pour cette raison qu'on a l'autre inclusion de la présentation classique du problème, juste pour cette histoire de définition et du fait que lorsqu'on a P=NP cette idée de "réduction" d'un problème en un autre n'est peut être plus aussi claire qu'on imagine qu'elle soit. J'avoue que je ne sais pas si on pourrait reformuler les définitions pour donner un sens à cette intuition que vous avez que même dans un cas ou P=NP il y aurait des problèmes non NP-complet, je pense que si on cherche à le faire, on se heurte à des difficultés pour tracer la frontière entre qu'est ce qu'une réduction exactement. (Notamment le fait de pouvoir par exemple "résoudre X dans un premier temps, puis encoder dans une instance de K la solution, résoudre cette instance de K, puis ensuite la décoder dans le sens inverse si vous voyez ce que je veux dire).
@@PasseScience Merci beaucoup pour les détails, je ne suis pas un spécialiste et ma remarque était peut être un peu hâtive. Je vais lire attentivement votre commentaire et le transmettre à mon élève. Merci beaucoup
@@ericrougier4934 J'ai retrouvé je pense le raisonnement plus précis: Déjà il faut garder en tête qu'ici les classes de complexité sont définies pour des problèmes de décision, c'est-à-dire des problèmes dont la réponse sur une instance est oui ou non. Supposons que P=NP, et qu'on prenne dedans un problème K qui soit NP, on va montrer que K est NP-complet: pour se faire on prend un autre problème X dans NP quelconque et on va construire une réduction de X en une instance de K. Réduire ici ça veut dire "transformer X en une instance de K telle que la réponse du problème de décision sur K soit la même que la réponse du problème de décision sur X" Et ça peut se faire ainsi de manière pathologique: On prend une instance de K dont la réponse soit oui, nommons la K-oui, et une instance de K dont la réponse soit non, nommons la K-non. Ensuite on va définir notre réduction polynomiale d'une instance de X en une instance de K de la manière suivante: on résout X en temps polynomial (ce qu'on peut faire car P=NP) si la réponse est oui on dit qu'on transforme ce X en K-oui et si la réponse est non on dit qu'on transforme ce X en K-non. Et du coup on a bien construit une manière de transformer une instance de X en K, en temps polynomial, et telle que la réponse dans la version K soit la même que dans la version X. Et comme cette réduction existe pour tout X alors ce K est NP-complet. Mais bien sur, comme je l'ai dit, c'est un peu pathologique, ça n'a plus trop d’intérêt de parler de réduction polynomial d'un pb en un autre lorsqu'on a ce genre d'astuce stérile à disposition (ce qui arrive parce que P=NP).Voila voila, je pense qu'ici c'est suffisamment rigoureux pour comprendre pourquoi par convention on a adopté des définitions telles que si P=NP alors P=NP=NP-Complet, parce qu’on a pas trop le choix et que cette notion intuitive de réduction en temps polynomiale perd de son sens lorsqu'on peut aussi résoudre en temps polynomial.
C'est la première fois que je comprends ce que veux dire P/NP que j'ai vu tant de fois, parce qu'enfin ... pour une fois... on vois un exemple concret. merci ! Par contre toute la vidéo j'ai attendu de voir la transformation du problème du sac a dos en problème des 3 couleurs... peut-on esperer une petite vidéo bonus pour ça ? Merci.
Super vidéo, ça fait plaisir de voir des vulgarisateurs traiter de sujet comme la logique, la complexité, etc... Cependant, je me demande à quelle point elle peut être compréhensible pour quelqu'un qui ne connait pas du tout le sujet. Notamment pour le problème SAT qui peut rester assez flou sans aucune base de logique. Et comme l'exemple de réduction polynomiale (que je ne connaissais pas d'ailleurs, merci) et basé sur ce problème je ne sais si ça a pu être vraiment compréhensible pour tout le monde. Mais je pense que l'essentiel passe, à savoir les conséquence d'une preuve que P=NP (ou pas).
Oui le problème SAT est abstrait et pas forcement agréable pour ceux qui n'ont jamais manipulé de ou, et. Ça leur demandera plus d'effort mais je pense que ça reste abordable. Le truc c'est que comme habituellement pour être fidèle à mon type de contenu j'ai voulu aller un peu plus en profondeur et montrer une vraie transposition de problème, et sans SAT c'est bien moins compréhensible. Mes relecteurs non scientifiques (qui aiment bien réfléchir) ont compris le passage. Dans le pire des cas, on peut comprendre que je transforme un problème en un autre sans en maîtriser les détails, je préfère donner plus que pas assez et du coup tu vois toi tu as appris la réduction polynomial SAT->3Col :)
Bravo excellente vidéo ! Une des meilleurs explications de ce problème : claire et pratique ! Une question : dans le graphe représentant le problème SAT : si on relie les 3 noeuds du OU entre eux, ce n'est pas un OU eXclusif plutôt qu'un simple OU ?
C'est bien un OU logique usuel : si A et B sont vrais, les deux nœuds de gauche du OU prendront les valeurs neutre et vrai respectivement. Si ils n'étaient pas reliés, alors on pourrait avoir A et B faux, puis les deux nœuds neutres et le graphe serait valide.
Oui effectivement, merci ! Un noeud de gauche peut être faux, et l'autre neutre :) Et je réitère : cet exemple est vraiment bien choisi pour illustrer comment résoudre un problème revient à en résoudre un autre.
Trouver une seule solution (ou dire qu'il n'y en a pas) suffit. Mais tu peux faire encore moins, juste que le programme dise s'il existe ou non au moins une solution, meme s'il ne la fournit pas, juste formuler une réponse correcte à la question de son existence.
Bonjour, connaitriez-vous une étude ou un algorithme qui crée un graphe qui si résolue (avec le bon nombre de couleurs)donnera la décomposition d'un nombre en facteur premier ?
@Passe-Science Il n'existe donc pas encore un algorithme qui a été créer qui traduit un problème 3 graphes a la décomposition d'un nombre en facteur premier ou inversement.
Quand vous avez A x B = C alors vous pourriez écrire A B et C en binaire, et concevoir la multiplication comme une opération logique (sur chaque bit de A et de B). Du coup c'est un problème SAT avec juste autant de variable qu'il y a de bits dans A et B et une formule logique certainement assez longue. Et du coup c'est un problème de 3 coloriage.
@@PasseScience Bonjour, avec mon algo, j'arrive à donner avec certitude un intervalle de couleur avec le nombre de point et de ligne, mais une fois avoir fait ceci j ai trouvé comment réduire cet intervalle et cela me donne deux couleurs, ces deux couleurs sont indécidables comme pour le deuxième théorème de Gödel ou j'ai trouvé un lien. Serait t'il possible d'essayer à partir de ces deux couleurs en essayant une par une les possibilités.
En gros si j'ai bien compris la vidéo, on résoud ce problème si on trouve un algorithme pour colorier un graphe avec 3 couleurs (s'il est 3-colorable) en un temps polynômial.
Oui, tout à fait. Il te suffit de trouver un algorithme en temps polynomial pour n'importe quel problème dit NP-complet (le 3 coloriage de graphe en est un exemple, il en existe beaucoup d'autres) pour demontrer que P=NP. (et donc répondre à la question "P=NP ou P!=NP?")
Bjr, et si un jour on resoud l'un des problème np en temp polynomial, la clique par exemple ou le sac a dos, somme nous tjrs loin de démontrer p=np car les problème sont différents, ou bien résoudre un seul problème suffira ???.?
Hello, justement, un des points que la video explique cest que tout problème np peut se reduire à un pb np-complet de notre choix. Les pbs np-complet sont par définition des problèmes qui, en fait, représentent tous les autres. Donc un seul exemple d'algorithme polynomiale sur un seul pb np-complet demontre p=np et fournirait un algorithme pour tout autre pbs.
@@adelazerty8046 Vous craignez que "non" quoi? pouriez vous détailler précisément le point ou la propriété qui vous semble incompatible avec mes dires. ?
Nn je ne parlais de vos dires mr, mais parexple karp a définis 21 problemes différent , la résolution certains peuvent mener a résoudre d'autre mais une génératrice qui règne le ts j'en doute, ce qui mènera a p=np mais c indémontable
@@adelazerty8046 Je crois que vous ne maitrisez pas les definitions des termes. Un probleme est dit NP-complet precisement lorsqu'on peut reduire en lui n'importe quel autre pb NP. (Ce n'est pas un avis ni un theoreme c'est une definition). Les 21 problemes que vous citez sont ceux la: fr.wikipedia.org/wiki/21_probl%C3%A8mes_NP-complets_de_Karp et il s'agit bien de problemes NP-complets. Vous pouvez voir sur la page en question "qui sont réductibles entre eux" ce qui veut precisement dire qu'on peut passer de l'enoncé d'un de ces problemes à un enoncé sous la forme d'un des autres à loisir. La page wikipedia eng donne un peu plus de detail: en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems. Autant le concept de NP-completude est une definition autant le fait qu'il existe des problemes NP-complets est en effet pas du tout trivial. Pour demontrer cela il a suffit historiquement de donner un exemple de tel probleme c'est le théoreme de Cook ici: en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem. Ce theoreme montre qu'en particulier le probleme SAT est bien tel que tout autre probleme NP puisse etre ramené à lui. (et comme je le disais ce n'est absoluement pas trivial). Ensuite une fois qu'on a eu un tel exemple de probleme NP-complet il est facile de trouver d'autre problemes qui sont dans cette classe, il suffit de demontrer qu'on peut transformer un enoncé du pb SAT en eux. C'est ce qui a été fait pour les 21 problemes de votre liste, ils sont tous equivalent à SAT et donc tous NP-complet, et donc par definition trouver un algorithme pour l'un d'entre eux, n'importe lequel, vous donnerait moyen de resoudre tous les autres parmi les 21 ainsi que tous les problemes de la classe NP (incluant ceux qui ne sont pas NP-complet mais juste NP). Vous avez une question particuliere sur un point?
Excellente vidéo! Je n'avais jamais vraiment compris ce problème qui fait partie des 7 du millénaire, merci! Au fait nouvelle vidéo sur ma chaine, à propos de l'utilité des maths, n'hésitez pas à passer :)
Salut, super vidéo ! En revanche quelque chose m'échappe. Tu expliques à 6:10 que "si un problème est NP complet, alors n'importe quel problème NP peut être transformé en une version de ce problème en temps polynomial". Imaginons un problème NP résoluble par un algorithme de complexité n^3. Cela veut-il dire qu'on peut le transformer en un problème NP complet de complexité n^2 par exemple ? Si c'est le cas, cela veut dire qu'il n'est pas de complexité n^3 mais n^2 du coup ... Je pense que quelque chose m'échappe dans mon raisonnement mais je ne vois pas quoi.
Hello, tu peux voir la classe NP comme "les problèmes moins durs que bidule" et dans la classe NP tu as les problèmes NP complets que tu peux voir comme du coup "les problèmes moins durs que bidule mais au moins aussi dur que truc". Avec cette vue oui tu peux prendre un problème en n^3 dans NP par définition, mais il est surtout dans le sous ensemble P de NP. Et oui tu pourras le transformer en un problème NP complet, enfin plus précisément te ramener à l’énoncer d'un problème NP complet qui, si resolu, te donnera la solution de ton problème. Cependant ça sera très "bizarre" de le faire car faire la correspondance sera plus couteux que de directement le résoudre, et si ça se trouve la correspondance te donneras directement la solution et sa version problème NP complet ne sera qu'un "prétexte" et sa solution même pas "utilisée". Par contre dans la suite tu parles de problème NP complet en n^2 et ça par contre c'est impossible, enfin on conjecture que ce n'est pas possible, qu'il n'y a aucun NP-complet dans P. (Voir les schémas autour de 9:50). Mais si jamais on en trouve un seul dans P alors une conséquence est qu'ils y seront tous et que P sera le même ensemble que NP.
La partie sur "peut on faire beaucoup mieux que tester un à un des candidats pour trouver une solution" ? Oui bien sur sur le plan théorique on pourrait imaginer beaucoup de choses exotiques, en pratique par contre lorsqu'il existe de bons algos ils se ramènent quasi toujours à un parcourt exhaustif d'une sous arborescence. Juste pour être sur qu'on parle de la meme chose tu peux me donner un exemple de complexité sous-exponentielle? (pas d'exemple de pb, juste un exemple de fonction de complexité)
@@PasseScience Bonjour, le problème d'isomorphisme de graphe (qui n'est pas connu pour être NP-Complet ni P), se résout en temps sous-exponentiel et même récemment a été trouvé un algo en temps quasi-polynomial ( O(exp(log(n)^cste) ). Ce qui est beaucoup, beaucoup mieux qu'un parcourt exhaustif. fr.wikipedia.org/wiki/Problème_de_l'isomorphisme_de_graphes Du coup imagine tu trouve une réduction polynomiale, d'un problème NP-Complet vers l'isomorphisme de graphe, on est bien.... ;)
@@librepenseur250 Tres intéressant cette classe GI, je ne l'avais encore jamais croisée. En effet pas mal d'espoir s'allume avec ce type de cas particulier. Il faudrait que je fouille un peu dans le papier de László Babai pour voir si l'algorithme quasi-poly est un algorithme utilisable en pratique et si on arrive à interpreter ce qu'il fait. Merci :)
@PasseScience bonsoir, j'ai sorti une vidéo sur la détermination d'un algorithme polynomiale pour le coloriage de graphe, j'ai fait une démonstration rigoureuse. J'espère que vous pourriez y getter un cou d'œil.
Voici le benchmark dont je parle dans mon commentaire sur votre chaine, il renvoie quoi votre algorithme sur les graphes donnés ? cedric.cnam.fr/~porumbed/graphs/
@@PasseScience Mais ce sont des graphes aléatoires ou ils sont toujours définis juste pour savoir, car s'ils le sont, j'aimerais pouvoir vous faire un algo qui génère puis qui résout en même temps. J'ai choisi de prendre C2000 et je reviens vers vous quand j'aurai fini de le coder, je le m'atterrais sur le drive.
@@resolution-de-probleme Je vous invite à faire une fonction qui lit les fichiers fournis par la page et les transforme en vos objets, pour automatiser la chose. Si j'ai bien compris ce sont des graphes pénibles pour les algorithmes de nombre chromatique. r1000.5 est plus intéressant.
@@resolution-de-probleme c2000 est un mauvais choix puisque l'objectif est de tester votre programme en comparant au résultat des autres et c2000 n'a pas de résultats dans le tableau... r1000.5 ou le450_25c sont plus intéressants.
Très bonne vidéo je m'abonne. J'ai juste une petite question: À 9:24 sur l'illustration P est inclus dans NP ce qui veut dire que tout problème rapidement résoluble est rapidement vérifiable mais du coup la non inclusion et l'intersection simple est-elle possible. En clair existe-t-il des problèmes rapidement résoluble mais pas rapidement vérifiable. Je me suis posé cette question, désolé si elle est débile. En tous cas je vais me regarder toutes les autres vidéos et attendre impatiemment les suivantes ;)
Non, elle est pas débile. Formellement, NP est la classe des problèmes rapidement résolubles, mais de manière non déterministe, c'est à dire en s'autorisant de "deviner" des solutions. Ainsi, si un problème est dans NP, il est résoluble par un algorithme "rapide" qui "devine" la solution, puis qui vérifie que cette solution est bien solution. Mais si un problème est dans P, il est rapidement résoluble, donc il est à fortiori rapidement résoluble de manière non déterministe. Ainsi, on a l'inclusion P dans NP. Je ne sais pas si j'ai été assez clair. La définition de NP dans la vidéo est bonne, et permet une meilleure compréhension. Mais je dois avouer que j'ai plus de mal à voir comment expliquer l'inclusion avec cette définition-là.
Merci pour cette explication, c'est un peu plus clair maintenant même si, je m'en doute, cela reste de la vulgarisation à mon niveau. Je suis très intrigué par les autres façons de définir P et NP. Je vais faire des petite recherches la-dessus. ;)
Merci beaucoup de votre explication claire! J’ai une question : Vous donnez 3 exemples des problems NP : le problème de 3-coloration, le problème du sac à dos, le problème SAT. En sens commun, on sait bien que NP et P sont différents, car au contraire à P, on n’a que des algorithmes exacts du type de la recherche par force brute en temps exponentiel, ou des algorithmes approchés en temps polynomial pour résoudre les problèmes NP. Pourtant si un problème NP est défini comme un problème dont la solution peut être rapidement vérifiable, alors un problème P est aussi rapidement vérifiable. Dans ce cas, comment peut cette propriété capturer la nature de NP qui est sensé être différent de P ?
Bonjour! merci pour votre intérêt dans cette vidéo. Je ne suis pas totalement certains d'avoir saisi votre question mais je pense que je vois. En gros vous vous demandez comment on peut RIGOUREUSEMENT définir la classe NP et définir la classe P sans avoir à l'avance de critère pour séparer les deux notions. (et sans se reposer sur l'intuition qui ne donne pas de rigueur formelle) Alors déjà, lorsqu'on rentre dans le cadre rigoureux, on n’étudie ici que les problèmes dit de "décision" c'est à dire formulé sous une forme ou la réponse est oui ou non. par exemple "puis je colorier ce graphe avec 3 couleurs?" (plutôt que de demander comment le faire à l'algorithme). Parmi tous les problèmes de décision, on définit 2 ensembles: Classe P: les problèmes tels qu'il existe un algorithme codable sur une machine de Turing universelle (Ça c'est la formalisation rigoureuse d'un ordinateur) répondant à la question en complexité polynomiale. Classe NP: pour non-deterministic polynomial, qui en gros se demande s'il existe un algorithme finissant en temps polynomial sur une machine de Turing non déterministe. C'est un peu subtile la définition rigoureuse de cette seconde chose mais, en gros, ça revient à doter la machine, d'une capacité de parallélisme infini, ce qui en forme vulgarisée revient à lui donner la possibilité de tester toutes les solutions en même temps. Donc on a bien 2 définitions rigoureuses, différentes, pour définir les deux classes, mais il se peut que ces définitions, bien que distincte, définissent un objet unique (si P=NP). Ensuite il y a la classe NP-complet qui est une surprise: on peut démontrer qu'il existe parmi la classe NP des problèmes particuliers tels qu'on puisse y ramener n'importe quel autre problème NP en temps polynomial. Ce n'est pas du tout évident au départ que la classe NP-complet n'est pas vide, c'est le Cook-Levin theorem qui donne le premier exemple de problème NP-complet. Ensuite une fois qu'on a cet exemple, c'est beaucoup plus simple après pour démontrer que d'autres problèmes sont NP-complets, il suffit de montrer qu'on peut les transformer en cet exemple precis, ou en d'autres problèmes qu'on a déjà transformer dans cet exemple. (ça c'est ce que je fais dans la vidéo). Ne pas hésiter à préciser votre question si je n'y ai pas répondu.
Merci beaucoup pour votre réponse rapide et patiente! Oui, j’attends à une définition formelle de NP qui soit cohérente avec le sens en commun : « Il n’y a pas d’autres voies qui s’offrent aux hommes, pour arriver à une connaissance certaine de la vérité, que l’intuition évidente et la déduction nécessaire ». - Descartes Vous expliquez : Classe NP: pour non-deterministic polynomial, qui en gros se demande s'il existe un algorithme finissant en temps polynomial sur une machine de Turing non déterministe. (Noter Définition 1) Le problème est qu’ici, la « machine de Turing non-déterministe » n'existe pas dans notre monde physique à ce jour ! Comme vous dites « ça revient à doter la machine, d'une capacité de parallélisme infini, ce qui en forme vulgarisée revient à lui donner la possibilité de tester toutes les solutions en même temps ». En plus, cette « machine » fait référence à « Oracle » dans le théorème de Cook (voir son fameux article en 1971 ). En fait, la définition informelle de NP (dont la solution peut être rapidement vérifiable) peut aussi être formalisée : - NP est une classe des problèmes vérifiables en temps polynomial par une machine de Turing. (Noter Définition 2) Il semble que ces deux définitions sont différentes de leur essence : Définition 1 sépare NP de P, mais elle est basée sur la « machine de Turing non-déterministe » imaginaire, tandis que Définition 2 est basée sur la « machine de Turing » réelle, mais elle confond NP avec P. En sens commun, bien que des différentes définitions d’un objet peuvent avoir le degré d'abstraction et le mode d’expression différente, mais elles devraient avoir la cohérence, c’est-à-dire, elles devraient désigner le même objet. Donc, mes questions sont: 1. Y a-t-il un problème avec les définitions de NP ? 2. La définition de NP est-elle liée aux difficultés pour comprendre le problème P vs NP (dans votre vidéo, beaucoup de gens expriment ce sentiment) ? @@PasseScience
@@yuli-ly7bd Bonjour, vous dites: "Définition 1 sépare NP de P, mais elle est basée sur la « machine de Turing non-déterministe » imaginaire, tandis que Définition 2 est basée sur la « machine de Turing » réelle, mais elle confond NP avec P." Déjà je pourrais revenir sur cette remarque parlant d'imaginaire qui est un peu douteuse car toutes les mathématiques sont des modèles abstraits, même le chiffre 1, et une machine de Turing déterministe est autant un modèle abstrait qu'une machine de Turing non déterministe. Parler même de complexité algorithmique c'est par définition un comportement à l'infini et c'est donc aussi un modèle abstrait, etc... Mais c’était juste pour la remarque, je ne vais pas trop digresser sur le sens ou l'absence de sens à déclarer que certains modèles mathématiques sont réels et d'autres non. Il y a ici plus court, pour réagir à votre paragraphe, il y a une confusion entre plusieurs choses. -1) Le problème de décision dans son intégralité, exemple "trouver la procédure pour répondre, quelque soit le graphe, à la question se demandant si chaque graphe est 3-coloriable ou non" On est au niveau dans l'ensemble infini des instances possibles de notre problème et c'est à ce niveau la qu'on peut parler de complexité algorithmique. -2) Se poser la question au niveau d'une instance de ce problème, c'est a dire ici pour un graphe donné. "Le graphe G est il 3-coloriable?" -3) Se poser la question pour une instance donnée et un candidat solution donné. Exemple: "La 3-coloration suivante "C" est elle une 3-coloration valide pour le graphe G?" Et si on veut parler de complexité dans ce cas 3 on va raisonner sur l'ensemble des instances graphe+candidat-coloration possibles. Et si on prend votre définition 2 pour NP, elle n'est en aucun cas la même que la définition de la classe P. Car elle ne porte pas sur le même niveau. La classe P c'est l'ensemble des problème de décision qui peuvent être RÉSOLUS en temps polynomial (c'est à dire qu'on ne fourni à l'algorithme que l'instance du problème, ici un graphe G, et il doit répondre en temps polynomial à la question est il 3-coloriable) La classe NP c'est l'ensemble des problèmes de décision qui peuvent être VÉRIFIÉS en temps polynomial. (et non résolus, c'est à dire qu'on fournit à l'algorithme une instance du problème, comme un graphe donné, ET un candidat solution. Le travail de l'algorithme est juste de se prononcer sur la validité du 3-coloriage fourni et non de conclure sur la 3-coloriabilite du graphe donné, qui pourrait être 3-coloriable d'une autre manière si le candidat coloriage ne convient pas). Donc pour la classe P et la classe NP il y a bien une notion de complexité polynomiale dans les deux cas, mais pas pour réaliser la même chose. Vous dite "Définition 1 sépare NP de P". Les définitions 1 et 2 sont mathématiquement équivalentes, donc si la définition semble "séparer" qq chose (ou qq soit votre conclusion a propos de la définition 1) alors la définition 2 fait la même chose. La définition 1 c'est une formulation en terme de RÉSOLUTION en temps polynomial sur une machine de Turing non déterministe, la définition 2 c'est une formulation en terme de VERIFIABILITE en temps polynomial sur une machine de Turing déterministe. Et comme je le présente ci dessus, ce n'est pas le même travail qui est qualifié de polynomial dans un cas comme dans l'autre. C'est plus clair?
@@PasseScience Merci beaucoup de votre patience ! C’est vrai que le mot «imaginaire» que j’ai utilisé pour désigner cette NDTM (Non-Deterministic Turing Machine) “un peu subtile”, est susceptible d’avoir l’ambiguïté. En fait il existe en général trois interprétations de NDTM : NDTM est une machine dotée d’une capacité de parallélisme infini ; NDTM peut être simulé avec TM en temps exponentiel; NDTM est une machine dotée de l’Oracle (dans le fameux article en 1971 de Cook). Donc, ce serait mieux de mettre de côté « Définition 1 » basée sur cette subtile NDTM pour l’instant, et rester encore un peu sur « Définition 2 ». En sens commun, NP et P sont différents, mais "Définition 2" dit : NP est une classe de problèmes vérifiables en temps polynomial par TM. Comme un problème P est également vérifiable en temps polynomial par TM, donc NP inclut P. On remarque que, la relation entre NP et P est passée de l’« opposition » à la « inclusion ». C’est pour ça que je demande : y a-t-il un problème avec cette définition de NP ? J’essaye d’expliquer ma question à travers une analogie : Je connaissait le «vache», mais pas le «cheval». Un jour je voyait un troupeau de vaches et un troupeau de chevaux ensemble dans une herbe : Yu demandait à Passe-Science : qu'est-ce que c’est ? Passe-Science : c'est le cheval. Yu : qu'est-ce qu'un cheval ? Passe-Science : un cheval est un animal ayant une couleur. Maintenant si vous me demandiez : tu sais ce que c’est un cheval ? Je ne peux que répondre: je ne sais pas, car une vache est aussi un animal ayant une couleur.
@@yuli-ly7bd Ha mais je comprend mieux ou se trouve la confusion, c'est complètement admis que P soit inclus dans NP par définition. Et par construction ça a toujours été le cas, et ce quelque soit la définition. Que ça soit selon la définition 1 ou la définition 2 P est inclus dans NP. Si un problème est P c'est trivial qu'il peut aussi être résolu en temps polynomial sur une machine de Turing non-déterministe (définition 1, et qu'il est donc aussi NP) et c'est aussi trivial qu'il est vérifiable en temps polynomial (définition 2, et est donc aussi dans NP). Il n'y a jamais eu "d'opposition" qq soit la définition, rien n'a jamais tenter de définir NP comme un ensemble disjoint de P, ça a toujours été une relation d'inclusion et ce qu'on cherche à savoir c'est si cette inclusion est stricte ou si c'est en fait une égalité, s'il existe le moindre élément dans NP qui ne soit pas dans P. Le cote disjoint ça serait plutôt pour la classe NP-complet, mais évidemment on en est pas certain (puisque c'est toute la question) NP-complet ce sont les problèmes qui sont dans NP et aussi en qq sorte "maximalement dur" ou "au moins aussi dur que". Si on a P différent de NP alors on aurait bien disjonction entre P et NP-Complet. Voir la vidéo à partir de 9:35 je montre les inclusions avec des patatoïdes.
J'ai du mal à comprendre en quoi l'exemple du sac à dos est un problème NP complet: s'il l'on prend le ratio ratio euro/kg minimal, que l'on sélectionne seulement les objets ayant ce ratio minimal et que l'on additionne leur prix, si ce prix est supérieur à notre prix voulu, le problème a une réponse positive façilement trouvable sinon non. Aurais-je mal compris le l'énoncé du problème?
Hello, tu as sans doute saisi l’énoncé du problème mais sous estimé sa "mécanique". Prenons un exemple plus simple: imagine que tous les objets pèsent autant que leur prix (5euros = 5kg), le problème reviendrait à juste se demander si on peut faire rentrer plus de x kilos dans le sac sans dépasser le max autorisé. On peut encore simplifier en mettant notre objectif exactement égal à la capacité du sac. Et le problème devient: Etant donné un ensemble d'entiers strictement positifs, est il possible d'en trouver un sous-ensemble dont la somme serait S ? (un entier objectif donné). Par exemple: -y a t il un sous ensemble de {1,2,5} dont la somme est 7? et la réponse est oui 2+5. -y a t il un sous ensemble de {1,2,5} dont la somme est 4? et la réponse est non. Donc pour cette version très simplifiée, ce cas très particulier du problème ou tout tes ratios sont égaux et ou on vise une somme exacte donnée, comment tu t'y prendrais pour donner une réponse rapide à la question? quel serait ton algorithme?
Les meilleurs algo pour la coloration de graphe par exemple ? C'est quoi ? e^n ? Tu as des liens qui explique l'algo ? Je serais curieux de comprendre ce qui le rend si compliqué que ça a résoudre !
Ca sera en a*b^n oui avec a,b des constantes plus ou moins grandes en fonction de l'algo. Ce qui rend difficile l'algo, comme dans tous les autres pb NP-complet c'est le caractère non local de tes décisions, c'est a dire que décider de colorier un nœud d'une couleur peut te forcer à en colorier 30autres d'une certaine couleur, puis reprendre une décision va t'en faire colorier 30autres, et la tu va te rendre compte que le dernier des 30 est incompatible avec un des nœud déjà colorié du coup tu va devoir tenter autre chose, et le problème c'est qu'on ne sait pas faire autrement que "tenter". On va éliminer tous les cas "locaux" ou on sera sur que ce n'est pas possible ou sur que ca "change rien" mais il va rester des trucs dans le genre ou une décision peut se rependre dans le problème et n'avoir des conséquences que tard, qu'on ne sait pas prévoir autrement qu'en essayant.
8 ปีที่แล้ว +1
En pratique, on utilise plutôt des heuristiques qui sont des algorithmes qui fournissent toujours des solutions mais pas forcément des solutions optimales : des coloriages à quatre couleurs quand trois peuvent suffire par exemple. Si ça t'intéresse, tu peux regarder du côté de DSATUR entre autres :)
Salut, excuse moi de poser une question stupide mais je ne comprends pas comment on pourrait démontrer que NP implique P parce que si tu as P il est facile de vérifier NP mais comment tu peux vérifier un problème facile à vérifier s'il n'a même pas été résolu?
@@mistereasy59 ah merci, il me semblait bien que c'était un énorme problème, d'ailleurs il y a plusieurs chose que nous avons du mal à imaginer que nous puission un jour démontrer, alors pourquoi ne pas en faire une loi? Sans doute, parce que pour les mathématiciens ainsi que pour ma part c'est assez frustrant de juste admettre une égalité...
Hello @JeSuisTonPierre, je ne suis pas sur d'avoir saisi la question alors je l’interpréte de deux manières tu choisis: tu demandes comment on a réussi à démontrer qu'un problème NP (non deterministic polynomial) était P (polynomial) ? réponse: on a jamais réussi à faire une telle chose, c'est comme le dit @mistereasy59 tout le cœur du problème, on ne sait pas à l'heure actuelle si P=NP ou P différent de NP. On a jamais réussi à démontrer P=NP mais on a jamais réussi à démontrer le contraire non plus. L'avis général c'est qu'il semble plus probable que P soit différent de NP. Autre interprétation de la question: tu demandes à quoi pourrais ressembler une preuve que P = NP, ie l'allure que ça pourrait avoir? he bien l'allure la plus simple consiste à juste trouver une manière alternative de résoudre un problème NP-complet en temps polynomial. Si pour un problème NP-Complet qcq on trouve une manière complètement différente de l'aborder et qui en trouve la solution en temps polynomial alors on saura que ce problème NP-complet est dans la classe P. Et la propriété magique du domaine c'est que si pour un seul problème NP-complet on trouve une preuve qu'il se trouve dans P alors tous les autres problème NP-Complet seront également dans ce cas.
bonjour je voudrais savoir suite à l'écoute attentive de ta vidéo si un simple problème qui consiste à trouver l'écriture d'un problème en terme équationnel rentrait dans la catégorie sac à dos des problème np complet? par exemple ''un père dit à son fils lorsque j'avais l'âge que tu as maintenant j'avais le triple de l'âge que tu avais , sachant que le père a actuellement 60 ans quel âge a actuellement son fils" je crois qu'une fois que l'on a réussit à réécrire le problème sous forme d'équation il est plus facile à résoudre mais je pense également qu'il est extrêmement facile à vérifier une fois en possession de la bonne équation.à ceux qui veulent trouver la réponse à cette énigme de mon cru je ne spoilerais pas ^^ si quelqu'un me réponds la bonne réponse j'irais juste confirmer ou non mais surtout la beauté de ce problème réside dans sa méthode de résolution... n'y allez pas à taton quoi
Traduire le problème en équation est avant tout un problème de linguistique et de sémantique. Donc c'est autre chose :) C'est une énigme rigolote qui a beaucoup de variations. Ton probleme rentre dans la categorie des systemes d'equations lineraires à N inconnues, et cela se resoud en temps polynomiale. Certes verifier une solution du systemes d'equations est plus rapide que d'en trouver une mais les deux taches (verifier ou trouver) reste ici dans la meme famille de complexite (la famille polynomiale) et dans le cadre de notre question P vs NP elles sont vues comme "aussi dures" l'une que l'autre (principalement parcequ'on les compares à des choses enormes).
Guillaume le cam votre solution pourra fonctionner à mon avi pour le pb n2, si on calcul le rapport poid dollard de chaque objet il suffit de prendre les objets avec le rapport le plus elevé
Merci bcp pour la vidéo. Sinon, quelqu’un peut me dire si ma compréhension est bonne: si on arrive à résoudre un problème NP complet alors on a résolu l’équation P=NP
Hello, oui c'est ça, si tu arrives de trouver un algorithme que tu puisses démontrer polynomial pour un seul des problèmes NP-complets alors tu resouds la conjecture par l'affirmative, ça démontrerait que P=NP.
Vous avez très bien construit votre vidéo, c'est clair ! J'ai juste un peux de mal au niveau du temps polynomial: comment la constante est déterminée ?
Tu veux dire comment on sait qu'un algorithme donné fini en temps polynomial?Je vais prendre un algorithme pour trier un tableau comme exemple: il existe plein de méthodes, l'une des plus mauvaise est la suivante: L'algorithme parcourt tout le tableau, cherche le maximum, le met en première position, et recommence exactement la même chose avec la suite du tableau (le re-parcourt, cherche le maximum et le met donc en 2eme position etc...) Au final cet algorithme va bien trier le tableau et il lui faut faire environ N+(N-1)+(N-2)+(N-3) etc... opérations (Parce que le premier coup il va parcourir les N éléments du tableau, puis un de moins etc). C''est la somme des entiers de 1 à N, cette somme vaut N(N+1)/2. Sous forme développée ca fait donc environ N^2/2 + N/2 opérations c'est bien un polynôme, cet algorithme de trie fait donc son travail en temps polynomial. Ça répond à la question?
+Passe-Science Oui merci pour la réponse ! C'est plus clair pour le temps polynomial. Mais en ce qui concerne le temps exponentiel ; par exemple avec le problème des noeuds, un algorithme qui crée toute les possibilités de mises en couleur, son temps sera calculé comment ? N le nombre de noeuds (et constante le nombre de couleurs ?)
Oui, pour un algorithme qui testerait tous les coloriages on voit que le nombre d’opérations nécessaire sera grossomodo le nombre de coloriages possibles. S'il y a N nœuds et K couleurs il y a K^N coloriages possibles. (Ce n'est pas un polynôme en N, c'est bien exponentiel ici). Dans la vidéo je parle de "temps" car c'est plus abordable, en pratique on préfère parler de nombre d’opérations.
Merci pour les encouragements. Oui peut être un jour je parlerais des autres classes de complexité mais a priori pas avant longtemps car c'est moins une question fondamentale :)
Il y a un truc qui me chiffonne : Un problème est NP-complet si on peut convertir n'importe quel problème en celui là. Mais vu que tous les problèmes NP ne sont pas NP-complet, ça implique que pouvoir transformer le problème A en le problème B ne signifie pas qu'on peut transformer le problème B en le problème A Dans ce cas, autant je comprend que s'il existe un problème P qui soit NP-complet, alors tous les problèmes sont P car on peut les transformer en celui-là, que je ne vois pas du tout en quoi ça les rend tous NP-complets PS : T'es sous-côté ^^
Hello pour le premier paragraphe oui tout à fait, tu peux voir un pb comme un ensemble d’énoncés et les pb NP-complet sont "suffisamment gros" pour qu'on puisse mapper n'importe quel ensemble issue d'un autre pb NP dessus. Un NP qui ne serait pas NP complet ne permettrait pas de trouver un mapping surjectif. (je suis pas super clair j’espère que c'est suffisant pour intuiter ce que je veux dire). Pour ton 2eme paragraphe, très bonne question et je m’étais posé la même à l’époque de la vidéo alors je te donne des éléments de réponse car je n'ai pas refermé ce dossier encore proprement. En fait déjà dans ma vidéo, je parle pas vraiment des classes NP NPC et P, je parle des classes FNP FNPC et FP en gros dans ma vidéo les pb sont des pb ou la solution est complexe, doit être décrite, on cherche des programmes qui ont comme output un truc riche. Alors que les pb de décisions c'est la version ou on force l'output du programme à être juste OUI ou NON. du genre plutôt que de se demander comment tri colorier un graphe, on se demande peut on le tri colorier. (et le programme doit juste dire oui ou non). Donc toi tu te trouver dans le cas ou NPC est dans E avec E = P = NP et tu te demandes pourquoi un truc qcq dedans aurait le pouvoir de pouvoir représenter n'importe quel autre problème, la réponse est en fait une arnaque: comme résoudre un problème qcq dans NP est maintenant faisable en temps polynomial, alors, pour le réduire en un autre de ton choix, tu peux commencer par le résoudre, une fois que tu l'as résolu et que tu sais donc si ton programme doit répondre oui ou non et ensuite tu peux mapper ton énoncé de force sur 2 cas particuliers du problème en lequel tu veux le réduire, un pour oui et un pour non. Donc en gros ta réduction est en fait une résolution suivit d'une réduction débile, comme la premiere se fait maintenant en temps poly tu as bien au total une réduction en temps poly. Mais clairement ici on a l'impression qu'on a perdu un truc plus subtile et a l'heure actuelle je ne sais pas si c'est possible de décrire le truc plus subtile auquel tu penses (et auquel je pense) ou on aurait une réduction qui a bien un sens, qui préserverait la structure, et si c'est possible je ne sais pas comment. Mon instinct en fait me dit pour le moment, que la possibilité de cette arnaque, rend impossible de definir proprement la "reduction" au sens ou on aimerait pouvoir la définir.
Hello, il y en a deux: Le premier est assez "simpliste" et peu dense, et quelque fois dans de rares passages pas totalement maîtrisé: www.amazon.fr/Physique-Quantique-enfin-expliqu%C3%A9e-simplement/dp/2953966315 Le deuxième est abordé de manière historique très riches en plus de la vulgarisation en soit, ça reconstitue le cheminement intellectuel j'ai beaucoup aimé: www.amazon.fr/Mod%C3%A8le-Standard-Physique-Particules-l%C3%89lectron/dp/2729880011
lorsque l'humain examine le problème il peux faire quelque chose que ne peux pas faire la machine c'est à dire regarder le problème dans sa globalité sans prendre les étapes une par une. Par exemple un ordinateur va observer des détails sur un visage pour le reconnaître tandis que nous en avons une vision globale avec donc logiquement une quantité infinie de détails. si on pouvait transférer cette intelligence globale à un ordinateur (peut etre avec un ordi quantique qui traite une infinité de donné a la fois).
Nous ne sommes que des machines, élégantes et évoluées, mais des machines tout de meme. Ce qu'on peut faire rien empêche un ordinateur de le faire, c'est une question de programmes. La vision "globale" que tu cites c'est un mauvais exemple car on fonction vraiment de la meme manière qu'un ordinateur pour le coup :) le deep learning ca fait par principe un truc vraiment très proche, nous aussi on dispose de couche de neurones qui filtre localement les details et les passent aux couches suivantes, l'impression de "globalité" dans notre traitement des choses n'ai lié qu'au fait que seul ce qui se passe dans les dernières couches ne soit interpretable par notre conscience. J'ai beaucoup suivi les péripéties du programme de deepmind alphago qui a historiquement battu pour la premiere fois un humain top niveau au go, et en tant que joueur en dan, je peux dire que ce que fait la machine est très proche de ce que nous humain faisons, et que s'il excelle dans un point c'est dans sa vision globale de la position, qui depasse maintenant la notre. Il y a encore une infinité de chose qu'un programme ne peut pas faire (c'est pas demain qu'un programme inventera un nouveau Alphago, il nous faut encore des humains pour inventer cela) mais il n'y a pas d'obstacles fondamentauxx :) On peut se demander ce qu'il se passera lorsque ca arrivera !
Passe-Science je suis d'accord sur le fait que nous fonctionons comme un ordinateur mais je pense qu'il y a une nette différence entre lui et nous c'est que nous humain sommes branché à "l'univers" comme si nous avions une connexion wifi avec l'infini que l'ordinateur ne possède pas car fabriqué par un être humain qui n'a pas conscience de sa connexion. (impossibilité de mentaliser l'infini) (oui je sais c'est carrément théorique et non scientifique mais je vois les choses comme ça)
pour moi il n y a pas de lien entre le fait qu un probleme soit rapidement verifiable et qu il soit rapidement soluble , je m explique si je connais le code secret d un cadenas a 10 chiffres (rapidement verifiable) je ne vois en quoi cela va m aider a demontrer comment deviner ce code..
Hello, l'analogie est intéressante mais la "différence" avec un problème mathématique donné c'est que dans le cas du cadenas il y a des règles du jeu assez claires "tu ne peux pas regarder dedans" (sinon très probablement déduire la combinaison est assez facile). Dans un problème mathématique, tu as tous les droits, tu peux t'y prendre comme tu veux, ce que l’énoncé du problème te donne comme information rapidement accessible est bien moins évident. D'autre part, dans le cadre de cette question P vs NP, on colle dans le même panier des choses qui sont pourtant très différentes: des temps "polynomiaux". C' est à dire que dans cette question on considère comme "aussi dur" résoudre un problème en temps linéaire (proportionnellement à la taille de l’énonce) et résoudre un problème en temps quadratique par exemple (proportionnellement à la taille du carré de l’énonce), c'est à dire que ça accepte que résoudre soit beaucoup plus long que vérifier, mais que ça reste dans la même "classe de complexité", en gros ce qui nous intéresse en résumé et qui n'est pas évident par rapport à l'exemple du cadenas c'est: peut on, en s'autorisant tout ce qu'on veut, trouver la solution d'un problème rapidement vérifiable d'une manière fondamentalement plus efficace que de tester toutes les combinaisons une par une (même si ça reste beaucoup plus long que de la vérifier). Et c'est cette question qui est encore irrésolue.
@@resolution-de-probleme Le problème avec ce genre de sujet, c'est qu'il y a de tres forte chance, que votre tentative soit "naïve" et des tentatives de démonstrations naïves e-mailée à des mathématiciens il y en a vraiment beaucoup. C'est pour ça que le plus important, pour avoir une suite, ça sera d’être modeste dans la forme, ne pas arriver en prétendant avoir la solution, mais plutôt demander d'en débattre ou de chercher ce qui n’irait pas dans l'approche etc... Meme si vous aviez le bon destinataire, si vous faite défaut dans la forme ça ira directement à la poubelle. Déjà ce que vous pensez avoir montré c'est dans quel sens de la conjecture? votre conclusion c'est P=NP ou P différent de NP? Je peux déjà faire une première passe ici, même sans vous risquer à donner des détails révélateurs, je peux juste regarder vaguement la structure global avec qq question pour voir à quel point c'est "crédible". Donc c'est P=NP votre conclusion ou le contraire?
Donc, si j'ai bien compris le problème du coloriage c'est le même que celui du sac a dos? ou alors C'est juste que les 2 sont transposables en problème SAT? Car j'arrive pas a faire le lien sinon.
Tout à fait ces 3 la sont NP complets (et il y en a beaucoup d'autres) donc par définition tu peux transposer n'importe quel problème NP (pas forcement NP complet) en chacun de ceux ci. Ce qui implique de pouvoir passer de un de ses 3 la à n'importe lequel des deux autres, et donc que oui 3-coloriage et sac à dos sont le même problème. Les transposition ne sont pas toujours triviales :)
Ah oué... ben merci d'avoir répondu déjà c'est super cool de ta part ;) Mais sinon le lien entre le problème du sac et du coloriage j'arrive pas a le faire perso. Peut-être en associant des couleurs au objets ? et encore O_o
Alors a priori en cherchant vite fait sur le web tu as ceci: staff.ustc.edu.cn/~csli/graduate/algorithms/book6/947_a.gif Chaque étiquette ramène à un problème NP-complet connu, et ceci represente des equivalences qui ont ete demontrees. Ie on peut transformer SAT and 3-CNF-SAT qui peut lui meme etre transformé en clique problem qui peut etre lui meme transformé en etc... puis en subset sum problem. Et ailleurs sur le web j'ai trouvé que tu peux transformer subset sum en sac à dos. Ce qui prouve la NP-completude de tout ce petit monde en admettant que CIRCUIT-SAT est NP - complet ce qui se demontre autrement. Donc sac à dos est NP-complet et peut donc représenter n'importe quoi d'autre avec, apres peut etre pas de maniere triviale si on a eu besoin d'autant d'etapes intermediaires ca peut donner une transformation velue.
Donc, si je comprends bien, on ne peut pas faire de transformation directe entre le problème 3-coloriage et du sac a dos, MAIS on peut les transposer en un autre problème commun ? probablement en problème abstrait comme le SAT (enfin, il l'est pour moi XD) Passionnant sinon. Complexe, mais passionnant ;)
Au niveau des transformations, méfie toi elles sont orientées. Lorsque tu transformes, comme on l'a fait dans la vidéo, SAT en un problème de 3 coloriage, tu démontres que un 3-coloriage est au moins aussi difficile que SAT et peut représenter au moins autant de problèmes que SAT. (parce que si tu sais résoudre 3-Col cette transformation, de SAT vers 3-Col, peut t'aider à résoudre SAT, mais si tu sais résoudre SAT cette transformation seule ne t'aide pas à résoudre 3-Col) La transformation en elle même ne te montre pas d’équivalence. Mais le truc subtile c'est qu'on dispose d'un probleme NP-complet on va dire "Racine" pour lequel on sait démontrer qu'il peut modéliser tous les autres. Donc en pratique tu peux te retrouver avec: (N'importe quel NP) -> Racine -> SAT -> 3 color -> Bob -> machin -> truc. Et donc après il est possible que la seul transformation dont on dispose pour passer de machin à 3-col soit: Machin ->Racine(par defintion) -> SAT -> 3 color. Rien empêche évidemment de trouver des transformations plus directes des raccourcis, mais c'est vrai que vu la tete des problèmes sac à dos et 3 color ça ne se ressemble pas, et pourtant c'est bien le même. :)
en gros ça veut dire que si P=NP je peux pirater tous les sites internet du monde :) ben oui si le problème SAT peut être résolu en tps polynomial, alors cela ne marche pas que pour les équations logiques simples... mais aussi pour les formules plus complexes comme trouver l'antécédent d'une fonction (avec des nombres entiers sous une valeur de 2^x, division donne nombre entier seulement)
Oui et non, car la complexite theorique ne renseigne que tres peu sur le temps pratique. Par exemple peut etre quil existe un algorithme en temps polynomial de la taille (et que du coup P=NP) qui conclut en un temps T=A*N^k (T le temps et N la taille de l'input) mais avec un A tres gros et un k tres gros, genre polynomiale de degré 1089 (k=1089) ce qui ne sert en pratique a rien du tout. Et ce qui est drole cest que j'ai souvenir d'avoir vu des exemples de problemes industriels pour lesquels ont a des solutions polynomiale mais qui en pratique sont beaucoup plus lente a etre trouve qu'avec l'algorithme exponentiel. (justement a cause de truc dans ce genre la, de grosse constante ou gros k)
Ayant beaucoup réfléchi au problème NP=P. Que j'ai instinctivement mis en lien avec l'interprétation de Hugh Everett du chat de Schrödinger , la Théorie du Chaos, Principe de Church-Turing-Deutsch. J'ai trouvé une voie où je penses que c'est possible. En introduisant la notion d'anti-hasard. Je m'explique. Si prend l'interprétation de Hugh Everett du chat de Schrödinger, notre univers ce scinderait en 2 à chaque choix possibles. Soit notre univers, celui où on vit comme Univers 0 à un temps de Planck donné. Celui donnerait naissance a une infinité d'univers parallèle. Prenons maintenant l'ensemble des univers crée de l'univers 0 et l'ensemble des univers crée par ceux là. Si on se place de notre point de vue nous pouvons voir qu'un seul chemin, qu'une suite de calcul possible. On pourrait comparer notre univers à une machine de Turing déterministe on a une transition possible. Par rapport a notre référentiel. Si maintenant on observe l'ensemble des univers dont l'univers 0, nous sommes dans le cas d'une machine de Turing Non déterministe, Chaque univers est une suite de calcul avec plusieurs transitions possibles. Cependant l'absurdité viens là, un tel ensemble d'univers où finalement tout se produit est déterministe. Donc de ce référentiel NP=P, car le non-déterministe extrême pousse au déterministe. Autrement dit la question ne serait pas de trouver une solution car on sait qu'elle existe mais pouvoir trouver la branche. Autrement dit La solution et la vérification s'équivalent dans cette infinité. NP=P si tout les choix peuvent être vérifié simultanément à la manière de l'ensemble de l'univers. Si le nombre de possibilité de vérification croit plus vite que le nombre de possibilité a vérifier.
Hello, je ne suis pas sur de tout suivre, mais je reviens sur quelques définitions/utilisation des termes. Dans l’interprétation de Hugh Everett c'est le monde subjectif qui est non-déterministe, ie étant donné ou on se trouve et ne sachant que cela (de notre point de vue) on ne sait pas ou notre branche va continuer. L'univers lui, en considérant toutes les branches est déterministe (ce sur quoi tu retombes lorsque tu dis "Cependant l'absurdité viens là"). Ça sera ainsi qu'on utilisera ces termes (pas dans le sens inverse), par exemple la mesure (en physique quantique) est subjectivement indéterministe (on, ne peut, nous, jusqu’à preuve du contraire, pas prédire son résultat), en revanche, la fonction d'onde (qui contient en elle toute les possibilités de résultats de mesure) est déterministe (elle a une évolution unique entièrement déterminée par l’équation de Schrödinger). Ensuite la question P=NP est une question mathématique, ce n'est pas une question physique. Pour le voir il suffit de remplacer le mot "Non-deterministic" par "infiniment parallèle". La question est de savoir, si un certains types de calculs qu'on peut résoudre en temps polynomial avec une capacité de calculs infiniment parallèle (autant d'ordinateurs qu'on veut), peut être également résolu sur un seul ordinateur (sans parallélisation) et également en temps polynomial. Lorsque tu dis "Donc de ce référentiel NP=P" par exemple, je ne suis pas sur que la notion soit maîtrisée/comprise.
Effectivement je partais du postulat que nombre d(ordinateurs/univers) est infini. Quand je dis dans ce référentiel NP=P. C'est plus que maladroit , ce que je voulais dire par c e "référentiel" c'est un référentiel où l'ont a accès aux donnés de toutes les branches, ainsi pour trouver une solution il suffisait de vérifier. En tout cas grâce a votre réponse je peux voir mes erreurs merci beaucoup.
Assume p is the fastest solution to my question And Np is the set of solutions that can solve the problem Then p = Np in one solution And p differs from Np in the remaining solutions. The correct answer can be checked But these same answers cannot be calculated quickly
Mais pourquoi P = NP est à 1 million $ ? Je veux, dire. Si on résoudait l'hypotèse de Riemann, on aurait la réponse aux nombres premiers, ce qui ouvrirait plein de porte aux mathématique! Mais P = NP, si on le résoud, toit ce que ça fera, c'est le résoudre. Ça ne sert pas à grand chose de savoir si P = NP.
Ça a plein de conséquences sur la compréhension de l'algorithmique, et plein de conséquences potentiellement pratiques sur le cryptage ou sur la résolution de problèmes.
Si P=NP, alors toute la cryptographie asymétrique actuelle s'écroule. En effet, elle est basée sur la notion de fonction à sens unique, c'est-à-dire une fonction dont le calcul d'un image se fait en temps polynomial, mais dont le calcul d'un antécédent se fait en temps exponentiel.
0:55 pour moi ça signifie évidemment que P≠NP ! J'ai mis 10 mois pour formaliser le paradoxe de Banach-Tarski (c'est long), mais mon logiciel assistant de preuve la vérifie en 4 minutes (c'est rapide). J'ai l'air de plaisanter mais c'est pourtant ce qui est dit ici. Et donc, je ne comprends pas en quoi la question de P=NP ou P≠NP est pertinente en soi. Mes collègues s'énervent à essayer de m'expliquer et moi je m'énerve à leur expliquer que ce problème m'est totalement incompréhensible.
Hello, ce qui est dit à 0:55 est "en gros" ce de quoi la question parle, mais lorsqu'on parle vraiment de la conjecture P vs NP on ne parle pas que de cette version "en gros" mais bien de quelque chose de tres precis mathematiquement. Si on reste dans les formulations "en gros" du problème il y en a une autre qui est interessante: "dire que P different de NP ça revient à dire que dans pas mal de problèmes, pour savoir si une solution existe, on a rien de plus intelligent que de tester 1 par 1 la "majorité" des candidats possibles." Par exemple dans le cas d'un graphe et ou la question serait "est il tricoloriable?" (voir vidéo) he bien meme sil y a des astuces algorithmiques, à la fin on semble avoir besoin de tester un nombre exponentiel de cas juste en les énumérant bêtement. C'est ca dans l'essence la question adressée derrière la conjecture, y a t il, dans un sens mathématique précis, mieux que d’énumérer et tester betement une par une la "majorite"(toujours selon un sens mathematique precis) des candidats pour savoir si l'un d'entre eux est solution du probleme? Dire que P different de NP c'est penser qu'il n' y a rien de mieux que cela, dire que P = NP c'est penser qu'il y a mieux. Mais on a jamais reussi à trouver mieux, et jamais réussi à demontrer que "mieux que cette enumération bete" n'existe pas. Voila voila.
@@PasseScience : ça veut dire que si on arrive à écrire un algorithme qui résout le problème du graphe aux trois couleurs en une complexité polynomiale, on aura montré que P=NP ? Et que si on démontre que quel que soit l'algorithme de ce problème précis, on trouve toujours des exemples de graphes qui se résoudront en un temps exponentiel (genre la diagonale de Cantor qui montre que quelle que soit l'énumération des réels, il s'en trouvera toujours un qui ne pourra pas y être), on aura prouvé que P≠NP ?
@@j9dz2sf roglo Oui tout à fait (en theorie c'est expliqué dans la video). Il suffit de le faire pour un seul des problemes dit NP-complets et oui le 3 coloriages de graphe en est bien un (la notion est egalement abordée dans la video ainsi que la raison pour laquelle le faire pour un implique que c'est valide pour tous). Voila voila.
@@PasseScience : du coup, je trouve que ça aurait été mieux si on avait appelé ça "problème du coloriage d'un graphe en 3 couleurs" plutôt que "P=NP" qui me parait peu parlant et très abstrait. Parce que le résoudre résout au moins quelque chose. Tandis que sous la forme "P=NP", on voit pas bien ce que ça résout. Même si c'est équivalent.
Très bonne vidéo. Par contre en tant que professionnel de l’informatique je dois dire que tant P = rapide est une notion de Math et pas d’info. En pratique O(n^2) c’est déjà lent et tous ce qui a un exposant supérieur à 2 est inutilisable pour des données non trivial. Il y aura forcément quelqu’un pour dire oui mai si le facteur est suffisamment petit… Ça veut simplement dire qu’il considère une taille de problème qui est très limité et donc des données triviales.
il aurait été fort utile de définir la notion de d'algorithme déterministe et non déterministe et de NP-difficile ----difficulté par rapport à une classe
C'est marrant je ne sait pas comment l'expliquer mais j'ai l'impression que le problème parle de lui-même, du genre si on galère à trouver la réponse à P vs NP c'est visiblement une question complexe ou il faut voir plein de possibilités et ça ressemble à P n'est pas égale à NP du coup reste plus qu'à le démontrer, mais on va galérer, ce qui semble être le cas vu qu'on ne l'a toujours pas trouvé. Après je dis probablement des bêtises puisque je ne suis pas sûre d'avoir compris le problème
Bonne video mais quand ça parle de NP complet avec l'exemple je trouve sa un peu compliqué à mon gout faut aller plus doucement et simplifier au maximum cet exemple
Salut, essaye de faire des vidéo de 40 min ou tu explique vraiment en détail un problème donné. Genre les outils mathematique pour le résoudre et de quelle manière de faire. Comme ça on comprendra vraiment la difficulté d'un problème.
Très bonne vidéo, avec plein de points intéressants, mais cependant je pense qu'on peut apporter une petite nuance entre les aspects théoriques et pratiques... En fait, l'archétype du problème NP-complet, c'est plutôt le problème SAT, et c'est vraiment un problème très étudié, beaucoup de gens ont élaboré des techniques de réduction redoutablement efficace, ce qui permet de programmer des solveurs SAT très rapides en pratique sur la majorité des cas. A l'inverse, pour beaucoup de problèmes polynomiaux, la fameuse constante qui se trouve devant l'exposant peut être tellement grand que le programme sera en pratique complètement inutilisable et échouera lamentablement sur des petits cas. La complexité nous dit que ultimement pour des très grandes valeurs d'entrée, SAT sera forcément plus long en moyenne, mais il s'agit surtout d'une notion théorique, et les algorithmes utilises en pratique ne correspondent en général pas aux optimaux théoriques... Mais ça demanderai sûrement une autre vidéo d'explications :)
P = NP Algorithme du cavalier : On divise un échiquier de 64 cases en carrés de 4 cases. On place ensuite le cavalier à une extrémité d'un bord puis, il s'agit d'appliquer la suite : (12+0) +(12+1) +(12+0) +(12+1)... +0: on saute un carré de 4 cases. +1: on saute vers le carré plus haut vers le centre le plus proche en suivant l'ordre horaire. Si on a comme postulat de départ que le cavalier n'a pour seules possibilités son déplacement en L, et qu'on doit suivre le mouvement horaire, on n'a par défaut qu'une possibilité par mouvement (mis à part quand il y a +0, ou +1, mais alors, le décalage reprend cette possibilité de mouvement). Si on suit un mouvement chronologique horaire, on arrive naturellement, grâce à l'algorithme, à la case 64 sans avoir recoupé une des cases. Donc, dans ce cas, P=NP.
La question qu'on serait en droit de se poser après une vidéo aussi difficile est: Faites-vous des sports de combats ? (je dis ça à cause des bras et du nez) Et si oui, pensez-vous faire une vidéo avec Scilabus ? Et très bonne vidéo, comme d'hab!
Haha:) , je suis censé laisser mon numéro la non? :P pas de sport de combat, mais une sorte de "street workout" de l'escalade (en salle) et beaucoup d'autres trucs!
+Passe-Science Ho cool ! Ca serait bien une vidéo avec Scilabus sur l escalade, avec comme sujet les énergies (pesanteur, cinétique), l'adhérence sur les prises etc. Ca pourrait être sympa de voir ce sport d un point de vue scientifique !
sinon dans le problèe de type sat tu pars du principe que le ou suppose d'avoir 2 éléments distinct et même ici parfaitement opposé, mais pourquoi ce présupposé? certe il remettrait en cause le problème mais on peut aisément imaginé que le ou soit placé entre 2 vrai représentés par des élements distinct à moins que la définition du ou en mathématique ne soit par soucis pratique plus restrictive qu'à l'accoutumé en français ce qui est surement le cas si comme tu l'as fais tu n'as pas pris le temps de l'expliquer.
Hum je ne suis pas sur de te suivre. Le "ou" mathématique c'est un opérateur logique qui combine deux variables booléennes, c'est à dire deux variables qui peuvent valoir chacune "vrai" ou "faux". Et la manière dont le ou combine ces variables c'est qu'il produit "vrai" si une des deux variables ou les deux valent "vrai" et qu'il produit "faux" si les deux variables sont à "faux". Ça répond à ta question?
mince je crois que je suis encore un peu plus embrouillé je crois que je vais reformulé (dsl je manque beaucoup de clarté dans mon propos :s) en gros (ce que je comprends du problème sat mais ptet que je me trompe) : (a ou b) et (c ou (non a)) soit a b et c doivent prendre les valeur vrai ou faux . Déjà je ne comprends pas pourquoi on peut transformer ce problème en un problème à 3 couleur car seul 2 valeur vrai et faux sont disponible. ensuite si on veut que sat soit un problème on doit bien définir le ou le et et le non. (hésite pas à me dire si je me trompes mais je les définis surtout en fonction de mon intution logique) donc pour moi le et veut juste dire rajouter une variable à un problème pour agrandir celui ci il n'a pas forcément fonction d'addition mais ajoute juste des données au problème . le non traduit juste un contraire d'une variable , si celle ci est comme ici binaire (2 choix) la valeur associée à une négation prends automatiquement l'unique autre variable disponible un ''non vrai '' implique un faux. ensuite le ou ici c'est plus compliqué je ne suis pas sûr de moi mais le ou traduit 2 possibilité or le ou doit être placé entre 2 variable à valeur différentes si on veut que le problème sat n'ai que 2 solution avec a vrai; b faux et c vrai ou totalement l'opposé a faux ; b vrai c faux. Or si le ou peut être placé entre 2 variables différentes prenant des valeur identiques le problème n'as plus de sens et a beaucoup plus de solutions. donc ma question portait sur le ou. Peut-il être placé entre 2 variable ( A B OU C) qui peuvent prendre la même valeur (vrai ou faux)? car si c'est le cas dans sa définition normale le problème n'a pas 2 solutions bien restreinte. voilà j'espère avoir été clair.
Le symbole "+" est un opérateur que tu connais bien. Il combine deux variables qu'on écrit de part et d'autre, par exemple "a+b". Pour fixer les idées on a qu'a dire qu'on parle des entiers. "+" est donc un opérateur qui prend 2 entiers et les combine pour faire un entier. par exemple 2+3 = 5. Jusque la tu me suis :) Bon maintenant parlons de "ou", "et" : ce sont également des opérateurs, seulement a la place de prendre des entiers en paramètres eux il prennent des booléens, c'est à dire des variables qui peuvent prendre comme valeur "vrai" ou "faux" et leur job et de combiner ses variables pour faire un nouveau booléen. (Exactement comme le + le faisait avec des entiers). "x et y" ça vaut "vrai" si et seulement si les deux variables valent vrai. "x ou y" ça vaut vrai si et seulement si au moins une des variables vaut vrai. De la même manière qu'on avait 2+3 =5 avec l’opérateur + dans les entiers on a donc par exemple: vrai et faux = faux, vrai ou faux = vrai, vrai et vrai = vrai, vrai ou vrai = vrai. faux ou faux = faux. avec les opérateurs "et" et "ou" dans les booléens. Donc ça devrait corriger/répondre à une partie de ta question. surtout ce que tu dis vers la fin sur "peut on placer le ou ....." ba on peut placer le "+" entre n'importe quels entiers. on peut placer le "ou" entre n'importe quels booléens. Le "non" c'est un opérateur qui ne prend qu'un booléen et le transforme en son contraire. Donc le problème SAT c'est en fait une équation ici c'est l’équation "(a ou b) et (c ou (non a)) = vrai". Il s'agit de trouver si elle a au moins une solution. (elle pourrait ne pas avoir de solution. par exemple "a et b et (non a) = vrai" n'a pas de solutions, elle pourrait en avoir plusieurs aussi on s'en fout on se demande si il y en a au moins une). Donc je reformule: le problème SAT consiste à se demander, étant donnée une formule logique (faisant intervenir des variables booléennes et les opérateurs et ou etc....), si on peut trouver des valeurs des variables qui rendent l'expression vrai (lorsqu'on la calcule avec les règles que j'ai donnée). C'est plus clair sur le calcul logique et le problème SAT? Pour ce qui est de le transformer en un problème de 3 couleurs ce n'est pas du tout facile à faire ni évident. maintenant que tu comprend mieux la question, je te suggères de te repasser lentement les étapes pour le faire (a partir de 6:30) dans la vidéo et de me dire ou tu bloques.
merci beaucoup en fait tu aurais peut être du dire tout cela dans ta vidéo mais c'est très clair maintenant merci beaucoup de prendre ton temps pour répondre à un abonné curieux et un peu perdu ;D
ptdrrrrrrrrr j'ai beau essayer, à chaque vidéo j'ai bien l'impression que malgré avoir bien écouté je comprends vraiment rien, enfin j'ai l'impression d'avoir compris alors que absolument pas..
Je penses que je n'ai simplement pas de connaissances assez poussés pour comprendre le fond de ce que tu dis, même si il est vrai que c'est très très intéressant, je penses que je ne vais pas tarder à totalement comprendre tes propos à force de te regarder !
tu ne dis pas aussi si même on arrive un jour à résoudre rapidement un problème np complet le temps pour transformer un problème en un autre n'en fera pas patir au final sa résolution.
Il s'agit principalement qu'une question de mathématique théorique dans laquelle ce qui nous intéresse c'est la "complexité" de l'algorithme de résolution. C'est à dire la manière dont le temps de résolution progresse avec la taille du problème. Dans le cadre théorique ici, transformer un problème en un autre, n'est autorisé et n'a de sens que lorsque la transformation prend un temps polynomiale car ce qui nous interesse c'est de distinguer les complexites polynomiales (qu'on regroupe dans la meme famille) des autres. Du coup dans notre cadre theorique, transformer le probleme ne fait en patir sa resolution dans le sens ou si on se trouve dans la famille "polynomiale" avec une transformation polynomiale on reste dans cette famille. Dans un cadre pratique cependant transformer un algorithme polynomiale en un autre algorithme polynomial ce n'est en effet pas du tout anodin! et transformer le probleme peut etre infaisable en pratique. La question théorique est importante en fait a la limite, il existera toujours une taille de probleme à partir de laquelle la transformation polynomiale d'un probleme NP en un autre sera negligeable par rapport au temps pour le resoudre. Mais il est tout a fait possible de n'avoir aucune applications pratiques :)
Dommage que la vidéo ne s'adresse qu'au personnes ayant des bases suffisantes . Peut être que j comprendrai mieux après avoir appris toutes les terminologies utilisée ici.
Hello, je t'invite à prendre la vidéo dans l'ordre et à me poser une question au premier moment qui nécessite des explications additionnelles, ainsi que sur la terminologie qui te pose problème. :) ne pas hésiter.
je pense que le raisonnement logique finira par battre ou surpasser le raisonnement mathématique sur tous les niveau (un jour), vous me direz que la logique est fait partie des mathématiques, je vous dirai que c'est exactement ca le pbm...
@@gnosetech5381 Donc pour vous le raisonnement est un cadre formel, et vous ne voulez pas appelez cela des mathématiques? je ne suis pas sur de saisir la nuance que vous voulez introduire ou la these que vous voulez amener avec cette opposition math/raisonnement.
Il vous manque peut etre un peu d'acquis de connaissance pour ce sujet... Je vous conseille soit de revoir la video, soit de chercher un peu plus sur le net!
Ouais tu devrais reprendre la vidéo et chercher les termes que tu ne comprends pas un par un si tu veux comprendre, Passe-Science est une chaîne se voulant à mi-chemin entre la vulgarisation et l'approfondissement de culture sur des concepts touchant aux maths et à la physique, c'est pas totalement de la vulgarisation, perso j'adore ce concept !
@44DexterMorga: N’hésite pas a poser une question précise, si tu reprends la vidéo, arrête toi au premier passage qui te pose problème et demande, je me ferais une joie de te répondre.
le problème c'est que pour formuler une question il faudra deja avoir quelque notion sur le sujet, sinon ma première question sera "mais de quoi tu parle ?!!!" loll alors je me demande plutot si vous pouvais me conseiller une documentation ou d'autres video qui servirons d'introduction pour les nuls , histoire de simplifier. bien que j'ai ete perdu sur ce sujet, je trouve vous vidéos génial, et merci pour ce que vous faite. :)
Ba en gros, il existe un problème mathématique très célèbre qui s'appelle P=NP. Je n'attend pas forcement à ce que les gens le connaissent c'est pour ça que je tente d'expliquer justement de quoi ça parle :) C'est pour ça qu'il me faut savoir ou tu plantes, par exemple si tu te concentre sur le passage diagramme 1:20 à 2:10, est ce qu'un truc te pose problème, si oui à partir d'ou?
Bonjour Monsieur Passe-Science,
en tant qu'informaticien je peux donner un avis éclairé sur cette vidéo de vulgarisation : elle est vraiment excellente ! Il me semble que pour présenter cette question complexe au grand public en seulement douze minutes, on ne pourrait pas vraiment faire mieux.
Merci beaucoup pour les encouragements!
meme avis, excellente video
d'ailleurs, en informatique, c'est pour cela qu'on développe les réseaux neuronaux a plein tube... le but etant qu'il vaux mieux avoir une reponse rapidement que la reponse la plus optimisé possible... (l'un n'excluant pas l'autre)...
en gros : pour cela, on colorie au hasard les noeuds... la ou ca marche on donne des points selon le resultat... puis on recommence... si par exemple le point A a recu beaucoup de point quand il etait bleu on aura tendance a le colorier bleu (toujours au hasard donc)... etc...
on peux aussi au bout d'un moment cree une sorte d'ADN regissant les relations entre les noeuds puis de le faire evolué de maniere plus """formel"""...
Bonjour,
Je vous conseil d'aller jeter un œil à mes vidéos aussi, si vous avez le temps. :)
Justement, un "avis éclairé" c'est quelqu'un qui n'y connais rien et qui, à la fin de vidéo peut déclarer ou non "j'ai tout compris !" et non pas quelqu'un "du milieu". Vous avez donc un degré quasi nul de légitimité pour juger de la qualité de vulgarisation de cette vidéo.
Oui sans l'ombre d'une hésitation c'est de très loin la meilleure vidéo en français qui explique aussi bien ce problème. Bravo
Merci beaucoup pour les encouragements!
excellente vidéo j'ai adoré tes exemples concret... sa serait cool si tu pouvais mettre a notre portée les 6 autres problèmes mathématique du millénaire ! du très bon boulot comme d'hab un GRAND merci
J'approuve cette remarque !
Les autres problèmes sont nettement plus complexes.
Tellement riche et intéressant quelle dommage que les mathématiques ne soit pas plus mis en avant l'importance de cette discipline est pourtant capitale !
J’avais vu là vidéo y’a 3 ans, j’avais rien compris, je n’étais encore qu’en terminale. Tout me semble maintenant beaucoup plus clair.
6:45, c'est vraiment une belle méthode et une belle mise en image, félicitation !
Super vidéo (comme d'habitude), Merci beaucoup !
Je suis ingénieur bac+5 en Maths appliqué et je suis admiratif de la qualité de vos vulgarisations qui contrairement à beaucoup d'autres rendent bien compte de l'essence du problème sans rentrer entièrement dans les détails mais sans le dénaturer non plus et sans dire de choses fausses et introduire des représentations mentales erronées, ce qui montre votre maitrise de ses sujets (je peux en tout cas le certifier pour vos vidéos sur les maths (Ex : groupe de gallois)).
Vous m'avez vraiment débloqué sur certains points en physique (notamment le spin), merci.
J'ai une question/conseil cela dit. Je ne comprends pas comment vous trouvez le courage de répondre à certains commentaires arrogants au possible où on sent dès le premier message qu'ils ne comprennent pas le sujet et qu'ils sont très probablement fermés à la discussion car ils n'ont pas envie de faire l'effort de comprendre (et n'ont d'ailleurs souvent même pas le niveau de comprendre pourquoi ils disent n'importe quoi). Vous écrivez parfois de longues réponses à ces personnes qui ne veulent pas reconnaître leurs torts alors qu'elles n'y connaissent rien et se sont à peine renseignées sur le sujet... Je l'ai vu plusieurs fois et le summum arrive sur cette vidéo (c'est aussi pour cela que je vous écris) où vous répondez des pavés à un collégien hautain et dé***. Comment avez-vous cette patience ?
Mon conseil si vous me le permettez : Ne perdez pas votre temps avec ces personnes-la !! Elles vont grandir/comprendre d'elles même plus tard si elles s'y intéressent vraiment. De plus, presque-surement, vos réponses ne serviront à rien et leurs réponses à eux risquent de vous frustrer. Identifiez-les (avec votre niveau de compétence, ça se détecte très vite) et ne perdez pas de temps à répondre ou en tout cas ne rentrez surtout pas dans le "débat". A la limite, si vous êtes courageux (ce qui me semble le cas ^^), expliquez dès votre 1ère réponse brièvement pourquoi ils ont tort, renseignez éventuellement les points clés à aller rechercher (pour permettre à d'autres personnes plus humbles et se posant les mêmes questions de trouver les réponses) puis oubliez-les !
Et encore merci pour la qualité de vos vidéos (un cran au dessus de beaucoup de vulgarisateur de cette plateforme) !
PS : D'ailleurs à titre personnel et purement subjectif : Etes-vous plus pro- P = NP (vous pensez que c'est vrai et qu'on arrivera à le démontrer un jour) ou pro P différent de NP ou encore que cette proposition est indécidable (dans ZFC) ?
Hello!
Sur P vs NP, j'imagine que la réponse doit être P différent de NP avec une démo pas très complexe, juste pas évidente à trouver (la réalité est souvent décevante) mais je préférerais que P=NP avec une démo bizarre ça serait très intéressant. Il y a beaucoup d'exemples en maths ou des comportements réguliers finissent par se briser, ca serait rigolo qu'on puisse résoudre n'importe quel pb NP complet en hardcodant juste 16 milliards de réponses et que la suite soit régulière et se ramène toujours à un de ces cas.
Oui je répond à beaucoup de gens mais ne vous inquiétez pas je ne suis pas naïf, je le fais: par disponibilité (j'ai pas masse de commentaire, en moyenne horaire moins de 1 par jour), par ennuie ou pour éviter de faire d'autre chose que je dois faire (une esquive psychologique qui me permet de tourner autour du pot), pour le public (il y a des gens qui passent par la et lisent les réponses), parfois juste parce que j'aime tenter de trouver les mots justes, parfois par curiosité sur la nature humaine et je me place à un niveau méta pour observer comment les gens réfléchissent argumentent et changent d'avis ou non (avec la personne dont vous parlez par exemple j'ai découvert me tromper complètement sur ses limites, en tout cas mal les évaluer, meme si c'est ultra naïf il a quand meme réussi à pondre un truc sur le pb des 3 couleurs qui à résolu mes 4 premiers tests de graphes, ca reprend la formule d'Audiard "un intellectuel assis va moins loin qu'un con qui marche", faut pas sous évaluer), et aussi dans une démarche sceptique pour voir si ma posture à autant de fondement que je ne pense (notamment dans les débats sous la vidéo sur l'évolution) et je suis toujours surpris de découvrir que ces fondements sont épistémologiquement bien moindre que je n'imagine, surtout lorsque le même jour je démonte une théorie fumée et que je répond à un mec qui "démonte" l'évolution, car ca me place des deux côtés et je peux remarquer d'énormes similitudes de méthodes qui ne devraient pas être la si ma démarche était aussi rationnelle que je pense. C'est un point qui demanderait des exemples mais ya un mec qui parle pas anglais qui me reprochait de lui demander de parler anglais pour avoir accès aux "preuves en faveur de l'évolution" et d'un autre côté je ne vais surtout pas aller apprendre l'arabe pour prendre connaissance des arguments du coran en faveur de l'existence de dieu. De prime abord on peut se dire que ca n'a rien à voir, mais en y réfléchissant on peut s'interroger sur les fondements de cette déclaration, pourquoi je trouve légitime à quelqu'un qui critique l'évolution de lui demander de prendre connaissance des arguments pour dans un langage (à la fois étranger dans la langue et étranger en technicité) qu'il ne maîtrise pas et que je trouve en même temps ma position à ne prendre connaissance de rien sur le coran tout aussi légitime. On va tenter de se répondre en disant "oui mais de mon coté c'est le consensus scientifique" mais est ce une bonne justification de croire juste comme le consensus? lui aussi crois en un consensus (juste d'une autre nature) etc... Ca confronte à un relativisme épistémique parfois aliénant. Ne vous inquiétez pas je ne remet pas vraiment en cause les conclusions, ca me permet de faire une introspection épistémique comme je le montre avec cet exemple pour illustrer une des raisons pour lesquelles je réponds, et on est très très surpris souvent lorsqu'on se prête à l'exercice. Du coup à terme on raisonne mieux et on a de meilleures curseurs de credence.
Vraiment de l'excellent travail ! C'est toujours hard tes videos mais c'est pour ça que je te suis. J'ai vraiment l'impression d'apprendre des trucs et pas de simplement survoler très legerement un sujet (choses rares pour les chaines youtube science)
Merci beaucoup pour les encouragements! c'est bien l'objectif de la chaîne. :)
Merci pour cette vidéo.
Excellent, ce sont des notions très abstraites et très verbeuses et tu les rends beaucoup plus abordables. C'est la première vidéo que je vois sur cette chaîne et je vais aller explorer les autres !
Merci beaucoup pour les encouragements. Sur des thèmes proches de celle ci il y a notamment l'axiomatisation, l'incomplétude, la machine de Turing, et biensur tous les autres thèmes j’espère peuvent aussi t’intéresser.
Bonjour, merci pour cette vidéo très claire. Je ne connaissais pas cette problématique avant la lecture du roman "Une machine comme moi" de Ian McEwan qui ne parle pas de ce sujet en profondeur mais qui l'évoque. Le roman parle d'un homme qui achète un robot qui a une apparence humaine et une forme d'intelligence très évoluée. Le narrateur rencontre Alan Turing qui, dans une version de l'histoire différente de la notre, n'est pas mort. J'ai lu des explications sur P vs NP sur Internet, mais aucune n'était aussi claire pour moi (qui ne suis pas mathématicien) que cette vidéo
Merci beaucoup pour les encouragements!
Bravo pour cette vidéo de vulgarisation très bien réalisée! Je suis étudiant en informatique et elle m'a beaucoup aidé dans mon cours de calculabilité. Continuez, moi j'adore!
Merci beaucoup pour les encouragements!
"une méthode(...), même bien foutue, (...)"
J'aime ce choix de terme technique :-)
Cette présentation est très claire et intéressante.
Bravo. Bien expliqué et illustré
Vidéo très bien faite et qui explique vraiment bien la question p=np. Merci à toi pour ces explications.
Merci beaucoup pour les encouragements!
De rien. Je sais que c'est toujours agréable d'avoir un commentaire encourageant, surtout quand on le mérite! Ce problème p=np m'a toujours intéressé et intrigué.
Chaine génial ! En tant qu'étudiant en 3 ème année de mathématiques grâce à vos explication et aux images que vous donnez , j'ai l'impression de mieux comprendre certain thème déjà abordé en cours ( Théorie des Ensembles, exct ... ). Continuez c'est vraiment très bien et très travaillé à mes yeux.
Ps: Es-ce possible de faire des vidéos sur les différents problèmes de Hilbert ou autres , car je trouve que voir les problèmes mathématiques récemment posé pour faire avancé les sciences sont très intéressant et de très bon thème a exploiter.
Merci beaucoup pour les encouragements!
Est ce que les théorêmes d'incomplétude de Kurt Godel pourrait impliquer que PNP ?
Non mais il est possible que l'on ne sache jamais si P=NP car certaines affirmations ne sont pas prouvable si falsifiables. P=NP pourrait être l'une de ces affirmations.
liké partagé. Merci C'est super ce que tu fais !
Bonjour ! J’ai du mal à me représenter la chose, est-ce qu’il est possible de transformer une grille de sudoku en un graphe à 3 couleurs ?
En tout cas, la vidéo a rendu le problème bien plus clair pour moi qui suis un piètre mathématicien. Merci beaucoup :)
Hello,
Oui on pourrait totalement transformer rapidement un sudoku quelconque en un problème de 3-coloriage, tel qu'une solution de ce dernier nous donne une solution du sudoku. On peut s'en rendre compte simplement (mais pas du tout de manière minimale) en utilisant l'exemple de la vidéo: on pourrait coder la valeur de chaque couleur de chaque case d'un sudoku sur plusieurs bits, et l'ensemble des contraintes sous la forme d'une grosse formule binaire à satisfaire (peut être énorme) et la vidéo montre ensuite comment représenter n'importe quelle formule binaire en 3-coloriage. Mais c'est juste pour se convaincre que c'est possible, y a certainement plus efficace pour reformuler un sudoku en 3-coloriage que de passer par des centaines de variables binaires :)
*Précision:* en général quand on s'intéresse à la transformation de problème c'est dans le cadre d'une question de complexité algorithmique pour les résoudre, on s'intéresse au nombre d'opérations élémentaires à faire en fonction de la taille de l'énoncé. Si le problème est un 3-coloriage on voit que cette notion de taille est triviale, c'est par exemple le nombre de nœuds du graphe auquel on s'intéresse dans la famille infinie des graphes pour lesquels on pourrait se poser cette question. Il peut y avoir des graphes de toutes les tailles, notamment des graphes aussi gros qu'on le désire et donc cette question de complexité prend un sens, puisqu'on peut du coup regarder comment évolue le nombre d'opérations d'un certain algorithme en fonction de la taille de notre énoncé. Si je dis ceci c'est parce que les "sudoku" ne sont pas une famille infinie d'énoncés, et qu'on a pas de notion de taille arbitrairement grande dans un sudoku, ils ont tous la même taille. Du coup se poser des questions de complexité algorithmique n'a pas de sens. Cependant on peut considérer que les sudokus sont une sous-famille d'un truc plus général: un problème de satisfaction de contraintes, similaire à un 3-coloriages, mais avec 9 couleurs, et des zones ou les couleurs similaires sont interdites plus complexes que simplement les voisins. Dans une telle famille généralisée on pourrait du coup se poser la question de la complexité algorithmique, et comme c'est clairement un type de problème ou vérifier la validité d'une solution se fait rapidement, (temps polynomial) alors c'est par définition dans la classe NP, et comme le problème de 3 coloriage est NP-complet, alors par définition on peut transformer toutes les instances de notre famille NP de problèmes en des instances de 3 coloriages équivalentes (et le faire rapidement en temps polynomiale)
Encore du très bon travail, tu mérites plus de visibilité :)
Merci beaucoup pour les encouragements!
cette vidéo semble d'excellente qualité
Continuez dans la vulgarisation, vidéo incroyable!!
Merci beaucoup pour les encouragements!
Kerbal Space Program en fond sonore, top
Bonsoir, connaissez-vous un article qui prouve ce qui est dit dans la vidéo avec l’exemple de la coloration de graphe? Merci encore.
Prouve quel point exactement?
@@PasseScience si on résout un problème NP complet en temps polynomial alors p=NP ou sinon p≠np
@@resolution-de-probleme Eh bien ceci ca vient de la propriété des problèmes NPC: comme vous pouvez transformer n'importe quel problème NP en une version du problème NPC de votre choix et le faire en temps polynomial, alors forcément il suffit d'en résoudre un seul NPC en temps poly pour démontrer que P=NP puisqu'ensuite vous pourriez prendre n'importe quel problème NP, commencer par le convertir en temps poly dans le problème NPC pour lequel vous avez une solution poly puis utiliser cette solution poly. Si vous demandez comment on démontre qu'il y a des problèmes NPC (c'est à dire des problèmes dans lesquels on peut transformer en temps poly n'importe quel autre NP en eux) il suffit de démontrer cette propriété pour un problème particulier, le problème SAT, c'est la theoreme de Cook:
fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Cook
Dans un second temps si vous voulez démontrer la NP complétude d'autres problèmes que SAT il suffit de montrer qu'on peut transformer SAT en eux comme je le fais dans la vidéo en transformant SAT en un problème de 3-coloriage (ce qui montre donc que tout problème peut aussi s'exprimer en probleme de 3-coloriage puisque d'après Cook tout problème NP peut s'exprimer en SAT, on en deduit du coup que le 3 coloriage est aussi NPC)
J'avais rien compris en licence sur ce sujet. Visiblement vous expliquez beaucoup mieux ce sujet, j'ai tout compris :D
Merci beaucoup pour les encouragements!
super video!
Belle vidéo, j'ai dû écouter une deuxième fois la réduction SAT → 3-coloriage pour comprendre, mais c'est clair et bien présenté :) Mais voilà des décennies que des gens très brilliants essaient sans succès de démontrer que P ≠ NP ou que P = NP (je viens de voir sur wikipédia que c'est peut-être indécidable aussi), alors il est très peu probable que je puisse y arriver même avec beaucoup de soirées pluvieuses à disposition (＾▽＾)
En fait faut se méfier de cela, par exemple une possibilité simple pour qu'un "lambda" comme nous prouve ce genre de chose, ça serait que P=NP et que sur un des problèmes NP complet connus on trouve juste un algorithme rapide auquel on aurait pas pensé. Apres si P ≠ NP il peut y avoir des arguments diagonaux et courts qu'il faut juste trouver, et ça tout le monde peut le faire, sisi, après si la seule démonstration possible est une démonstration technique de 30 pages, oui ça ne sera jamais à notre portée. :) "Beaucoup de gens ont essayé" je dis toujours que lorsqu'on dit cela, on compte toujours dans la statistique le beaucoup de gens qui étaient comme nous, du coup il faut tenter nous aussi ! parce que si on trouve normal de les comptabiliser, on doit trouver normal de s'inclure dans le processus de recherche, au pire on risquerait de trouver!
Et si je ne me trompe pas, il y a une sous-catégorie dans la catégorie NP-complet, ce sont les problèmes quantum-resistant car certains peuvent être résolus par un ordinateur quantique en temps polynomial. Je me demande si cette classification est bien claire, quels sont les problèmes qui sont quantum-resistants et lequels ne le sont pas. J'en connais quelques un dans ces 2 catégorie en cryptographie mais je n'ai pas une vue au-delà ... j'aimerais savoir.
Je n'ai trouvé que ceci sur la notion: en.wikipedia.org/wiki/Post-quantum_cryptography
10:16 sous-titres : "pour initiés" !
Super vidéo et problème intéressant !
Bonjour,
Merci pour la video, tres interressant!
J'ai une petite question minute 10:02. Pourquoi si NP-complet = P => NP-complet = P = NP ?
Merci
Christophe
Hello. Par définition P est inclus dans NP, et NP-complet est une sous partie de NP avec une certaine propriété: ce sont les problèmes à qui on peut ramener en temps polynomial n'importe quel problème NP. Ce n'est pas du tout évident que cette propriété existe c'est juste un fait mathématique: il y a une famille de problèmes à qui on peut ramener n'importe quel problème de la classe NP en temps polynomial et on appelle ces problèmes NP-complet). RQ: comme n'importe quel pb NP-complet est aussi un problème NP par définition ils sont aussi équivalents entre eux: c'est à dire qu'on peut passer d'un problème NP-complet à un autre de notre choix en temps polynomiale. Ainsi si le moindre problème NP-complet peut être résolu en temps polynomial alors, n'importe quel autre problème NP pourrait être résolu en temps polynomial (puisque par définition on pourrait dans un premier temps se ramener à celui qu'on sait résoudre rapidement). Et si n'importe quel NP peut se résoudre en temps poly alors par définition NP inclus dans P. Si NP inclus dans P alors que P inclus dans NP et bien les deux classes sont un seul et même ensemble. Il y a un des points qui n'est pas clair?
Hello,
Merci beaucoups pour la reponse, je pense avoir compris la nuance dans la definition de NP-complet ("il y a une famille de problèmes à qui on peut ramener n'importe quel problème de la classe NP en temps polynomial et on appelle ces problèmes NP-complet").
Je pensais avoir compris que les problèmes NP-complet étaient uniquement une classe de problèmes simplifiables .
Mais, si J'ai bien compris, les problèmes NP-complet sont en fait des problèmes qui permettraient de résoudre aussi les problèmes de classe NP en temps polynomial. D'ou NP-complet = P => NP = P
J'espere avoir bien compris :)
Encore merci pour vos videos!!
Oui voila, les problème NP-complets sont ceux en qui tu peux transformer n'importe quel autre pb NP (en temps poly).
merci mec j'ai un exam de complexité demain matin
Très bonne vidéo. Merci
Bonjour, merci pour votre vidéo, elle est très pédagogique et je l'ai montrée à mes élèves. L'un d'entre eux m'a fait remarqué à raison qu'il y a une petite erreur autour de la 10ème minute quand vous dite qu'il se peut que NP_Complet=NP=P. En effet, on aura toujours NP_Complet strictement inclus dans NP (tous les problèmes NP ne sont pas NP_Complets...)
Hello, merci pour les compliments! pour le reste je maintiens ma version :p, le diagramme que je montre est similaire à celui de Wikipedia ici:
en.wikipedia.org/wiki/P_versus_NP_problem#/media/File:P_np_np-complete_np-hard.svg
issu de cette page:
en.wikipedia.org/wiki/P_versus_NP_problem
dans lequel on voit que dans l'hypothèse ou on aurait un exemple de NP-complet dans P alors P=NP=NP-complet.
Mais je pense que je comprends votre étonnement, car initialement on sait que: P inclus dans NP, et NP-complet inclus dans NP. Si on exhibe un élément de NP-complet qui soit dans P alors instantanément on a une autre inclusion: NP inclus dans P. Ce qui amène à un diagramme ou on a un gros ensemble P=NP et dedans un ensemble potentiellement plus petit comme vous dites, les NP-complets. Alors pourquoi Wikipedia et mon diagramme montre aussi l'égalité NP = NP-complet dans ce cas ou P=NP? he bien je pense que ça vient des définitions rigoureuses de ces classes: un problème sera dit NP-complet lorsqu'on peut réduire en lui n'importe quel problème X en temps polynomial, et je crois me souvenir que ça se décrit plus précisément en terme de machine de Turing et de sous routine (on s'autorise le droit d'appeler le solveur du problème NP-complet). Cependant lorsqu'on a NP=P cette "réduction en temps polynomiale" devient un peu pathologique, car étant donné un problème K dans NP quelconque et un autre problème X dans NP lui aussi quelconque on peut utiliser le solveur de K pour résoudre X de la manière dégénérée suivante:
On résout X en temps polynomial.
On appelle le solveur de K pour ne rien faire.
et on a donc au final la solution de X. Et K est donc "NP-complet" dans la mesure ou en connaître un algorithme de résolution polynomial permet d'avoir un algorithme polynomial pour X.
Donc je crois que c'est pour cette raison qu'on a l'autre inclusion de la présentation classique du problème, juste pour cette histoire de définition et du fait que lorsqu'on a P=NP cette idée de "réduction" d'un problème en un autre n'est peut être plus aussi claire qu'on imagine qu'elle soit. J'avoue que je ne sais pas si on pourrait reformuler les définitions pour donner un sens à cette intuition que vous avez que même dans un cas ou P=NP il y aurait des problèmes non NP-complet, je pense que si on cherche à le faire, on se heurte à des difficultés pour tracer la frontière entre qu'est ce qu'une réduction exactement. (Notamment le fait de pouvoir par exemple "résoudre X dans un premier temps, puis encoder dans une instance de K la solution, résoudre cette instance de K, puis ensuite la décoder dans le sens inverse si vous voyez ce que je veux dire).
@@PasseScience Merci beaucoup pour les détails, je ne suis pas un spécialiste et ma remarque était peut être un peu hâtive. Je vais lire attentivement votre commentaire et le transmettre à mon élève.
Merci beaucoup
@@ericrougier4934 J'ai retrouvé je pense le raisonnement plus précis:
Déjà il faut garder en tête qu'ici les classes de complexité sont définies pour des problèmes de décision, c'est-à-dire des problèmes dont la réponse sur une instance est oui ou non.
Supposons que P=NP, et qu'on prenne dedans un problème K qui soit NP, on va montrer que K est NP-complet: pour se faire on prend un autre problème X dans NP quelconque et on va construire une réduction de X en une instance de K. Réduire ici ça veut dire "transformer X en une instance de K telle que la réponse du problème de décision sur K soit la même que la réponse du problème de décision sur X" Et ça peut se faire ainsi de manière pathologique:
On prend une instance de K dont la réponse soit oui, nommons la K-oui, et une instance de K dont la réponse soit non, nommons la K-non. Ensuite on va définir notre réduction polynomiale d'une instance de X en une instance de K de la manière suivante: on résout X en temps polynomial (ce qu'on peut faire car P=NP) si la réponse est oui on dit qu'on transforme ce X en K-oui et si la réponse est non on dit qu'on transforme ce X en K-non. Et du coup on a bien construit une manière de transformer une instance de X en K, en temps polynomial, et telle que la réponse dans la version K soit la même que dans la version X. Et comme cette réduction existe pour tout X alors ce K est NP-complet.
Mais bien sur, comme je l'ai dit, c'est un peu pathologique, ça n'a plus trop d’intérêt de parler de réduction polynomial d'un pb en un autre lorsqu'on a ce genre d'astuce stérile à disposition (ce qui arrive parce que P=NP).Voila voila, je pense qu'ici c'est suffisamment rigoureux pour comprendre pourquoi par convention on a adopté des définitions telles que si P=NP alors P=NP=NP-Complet, parce qu’on a pas trop le choix et que cette notion intuitive de réduction en temps polynomiale perd de son sens lorsqu'on peut aussi résoudre en temps polynomial.
J'aime le ton sur lequel tu parles tu expliques seulement les choses et non de manière arrogante.
bravo patrick, bonne continuation
C'est la première fois que je comprends ce que veux dire P/NP que j'ai vu tant de fois, parce qu'enfin ... pour une fois... on vois un exemple concret. merci !
Par contre toute la vidéo j'ai attendu de voir la transformation du problème du sac a dos en problème des 3 couleurs... peut-on esperer une petite vidéo bonus pour ça ?
Merci.
Merci pour les encouragements! Jette un oeil a la discussion avec "M.Evolite13" dans les commentaires.
Encore une vidéo très intéressante ! À quand une vidéo avec moi et science étonnante ? x)
Cool :D
j'ai essayé de dire ton nom pendant une bonne minute sans y arriver ^^
xD
Super vidéo, ça fait plaisir de voir des vulgarisateurs traiter de sujet comme la logique, la complexité, etc...
Cependant, je me demande à quelle point elle peut être compréhensible pour quelqu'un qui ne connait pas du tout le sujet.
Notamment pour le problème SAT qui peut rester assez flou sans aucune base de logique. Et comme l'exemple de réduction polynomiale (que je ne connaissais pas d'ailleurs, merci) et basé sur ce problème je ne sais si ça a pu être vraiment compréhensible pour tout le monde.
Mais je pense que l'essentiel passe, à savoir les conséquence d'une preuve que P=NP (ou pas).
Oui le problème SAT est abstrait et pas forcement agréable pour ceux qui n'ont jamais manipulé de ou, et. Ça leur demandera plus d'effort mais je pense que ça reste abordable. Le truc c'est que comme habituellement pour être fidèle à mon type de contenu j'ai voulu aller un peu plus en profondeur et montrer une vraie transposition de problème, et sans SAT c'est bien moins compréhensible. Mes relecteurs non scientifiques (qui aiment bien réfléchir) ont compris le passage. Dans le pire des cas, on peut comprendre que je transforme un problème en un autre sans en maîtriser les détails, je préfère donner plus que pas assez et du coup tu vois toi tu as appris la réduction polynomial SAT->3Col :)
Bravo excellente vidéo ! Une des meilleurs explications de ce problème : claire et pratique ! Une question : dans le graphe représentant le problème SAT : si on relie les 3 noeuds du OU entre eux, ce n'est pas un OU eXclusif plutôt qu'un simple OU ?
C'est bien un OU logique usuel : si A et B sont vrais, les deux nœuds de gauche du OU prendront les valeurs neutre et vrai respectivement.
Si ils n'étaient pas reliés, alors on pourrait avoir A et B faux, puis les deux nœuds neutres et le graphe serait valide.
Oui effectivement, merci ! Un noeud de gauche peut être faux, et l'autre neutre :) Et je réitère : cet exemple est vraiment bien choisi pour illustrer comment résoudre un problème revient à en résoudre un autre.
bravo. et merci!
bonjour , pour la résolution des nœuds colorés , il faut trouver un moyen de trouver une solution rapidement ou toutes les solutions?
Trouver une seule solution (ou dire qu'il n'y en a pas) suffit. Mais tu peux faire encore moins, juste que le programme dise s'il existe ou non au moins une solution, meme s'il ne la fournit pas, juste formuler une réponse correcte à la question de son existence.
Bonjour, connaitriez-vous une étude ou un algorithme qui crée un graphe qui si résolue (avec le bon nombre de couleurs)donnera la décomposition d'un nombre en facteur premier ?
@Passe-Science Il n'existe donc pas encore un algorithme qui a été créer qui traduit un problème 3 graphes a la décomposition d'un nombre en facteur premier ou inversement.
Quand vous avez A x B = C alors vous pourriez écrire A B et C en binaire, et concevoir la multiplication comme une opération logique (sur chaque bit de A et de B). Du coup c'est un problème SAT avec juste autant de variable qu'il y a de bits dans A et B et une formule logique certainement assez longue. Et du coup c'est un problème de 3 coloriage.
@@PasseScience Dans un problème SAT le nombre de couleurs du graphe engendre quoi ?
@@PasseScience Ou sinon pourriez vous me montrer comment on y arrive pour 6
@@PasseScience Bonjour, avec mon algo, j'arrive à donner avec certitude un intervalle de couleur avec le nombre de point et de ligne, mais une fois avoir fait ceci j ai trouvé comment réduire cet intervalle et cela me donne deux couleurs, ces deux couleurs sont indécidables comme pour le deuxième théorème de Gödel ou j'ai trouvé un lien. Serait t'il possible d'essayer à partir de ces deux couleurs en essayant une par une les possibilités.
En gros si j'ai bien compris la vidéo, on résoud ce problème si on trouve un algorithme pour colorier un graphe avec 3 couleurs (s'il est 3-colorable) en un temps polynômial.
Oui, tout à fait. Il te suffit de trouver un algorithme en temps polynomial pour n'importe quel problème dit NP-complet (le 3 coloriage de graphe en est un exemple, il en existe beaucoup d'autres) pour demontrer que P=NP. (et donc répondre à la question "P=NP ou P!=NP?")
Bjr, et si un jour on resoud l'un des problème np en temp polynomial, la clique par exemple ou le sac a dos, somme nous tjrs loin de démontrer p=np car les problème sont différents, ou bien résoudre un seul problème suffira ???.?
Hello, justement, un des points que la video explique cest que tout problème np peut se reduire à un pb np-complet de notre choix. Les pbs np-complet sont par définition des problèmes qui, en fait, représentent tous les autres. Donc un seul exemple d'algorithme polynomiale sur un seul pb np-complet demontre p=np et fournirait un algorithme pour tout autre pbs.
Je crains que nn mr, des problèmes de même classe de difficulté mais pas pareil dans les methodes de resolutions.
@@adelazerty8046 Vous craignez que "non" quoi? pouriez vous détailler précisément le point ou la propriété qui vous semble incompatible avec mes dires. ?
Nn je ne parlais de vos dires mr, mais parexple karp a définis 21 problemes différent , la résolution certains peuvent mener a résoudre d'autre mais une génératrice qui règne le ts j'en doute, ce qui mènera a p=np mais c indémontable
@@adelazerty8046 Je crois que vous ne maitrisez pas les definitions des termes. Un probleme est dit NP-complet precisement lorsqu'on peut reduire en lui n'importe quel autre pb NP. (Ce n'est pas un avis ni un theoreme c'est une definition). Les 21 problemes que vous citez sont ceux la: fr.wikipedia.org/wiki/21_probl%C3%A8mes_NP-complets_de_Karp et il s'agit bien de problemes NP-complets. Vous pouvez voir sur la page en question "qui sont réductibles entre eux" ce qui veut precisement dire qu'on peut passer de l'enoncé d'un de ces problemes à un enoncé sous la forme d'un des autres à loisir. La page wikipedia eng donne un peu plus de detail: en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems. Autant le concept de NP-completude est une definition autant le fait qu'il existe des problemes NP-complets est en effet pas du tout trivial. Pour demontrer cela il a suffit historiquement de donner un exemple de tel probleme c'est le théoreme de Cook ici: en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem. Ce theoreme montre qu'en particulier le probleme SAT est bien tel que tout autre probleme NP puisse etre ramené à lui. (et comme je le disais ce n'est absoluement pas trivial). Ensuite une fois qu'on a eu un tel exemple de probleme NP-complet il est facile de trouver d'autre problemes qui sont dans cette classe, il suffit de demontrer qu'on peut transformer un enoncé du pb SAT en eux. C'est ce qui a été fait pour les 21 problemes de votre liste, ils sont tous equivalent à SAT et donc tous NP-complet, et donc par definition trouver un algorithme pour l'un d'entre eux, n'importe lequel, vous donnerait moyen de resoudre tous les autres parmi les 21 ainsi que tous les problemes de la classe NP (incluant ceux qui ne sont pas NP-complet mais juste NP). Vous avez une question particuliere sur un point?
Bon travail !
Excellente vidéo! Je n'avais jamais vraiment compris ce problème qui fait partie des 7 du millénaire, merci! Au fait nouvelle vidéo sur ma chaine, à propos de l'utilité des maths, n'hésitez pas à passer :)
Salut, super vidéo ! En revanche quelque chose m'échappe. Tu expliques à 6:10 que "si un problème est NP complet, alors n'importe quel problème NP peut être transformé en une version de ce problème en temps polynomial". Imaginons un problème NP résoluble par un algorithme de complexité n^3. Cela veut-il dire qu'on peut le transformer en un problème NP complet de complexité n^2 par exemple ? Si c'est le cas, cela veut dire qu'il n'est pas de complexité n^3 mais n^2 du coup ...
Je pense que quelque chose m'échappe dans mon raisonnement mais je ne vois pas quoi.
Hello, tu peux voir la classe NP comme "les problèmes moins durs que bidule" et dans la classe NP tu as les problèmes NP complets que tu peux voir comme du coup "les problèmes moins durs que bidule mais au moins aussi dur que truc". Avec cette vue oui tu peux prendre un problème en n^3 dans NP par définition, mais il est surtout dans le sous ensemble P de NP. Et oui tu pourras le transformer en un problème NP complet, enfin plus précisément te ramener à l’énoncer d'un problème NP complet qui, si resolu, te donnera la solution de ton problème. Cependant ça sera très "bizarre" de le faire car faire la correspondance sera plus couteux que de directement le résoudre, et si ça se trouve la correspondance te donneras directement la solution et sa version problème NP complet ne sera qu'un "prétexte" et sa solution même pas "utilisée". Par contre dans la suite tu parles de problème NP complet en n^2 et ça par contre c'est impossible, enfin on conjecture que ce n'est pas possible, qu'il n'y a aucun NP-complet dans P. (Voir les schémas autour de 9:50). Mais si jamais on en trouve un seul dans P alors une conséquence est qu'ils y seront tous et que P sera le même ensemble que NP.
Bonjour, la fin à 11:17 n'est pas vraiment exacte, on peut imaginer avoir P!=NP et pourtant avoir un algo sous-exponentiel pour les problèmes NP.
La partie sur "peut on faire beaucoup mieux que tester un à un des candidats pour trouver une solution" ? Oui bien sur sur le plan théorique on pourrait imaginer beaucoup de choses exotiques, en pratique par contre lorsqu'il existe de bons algos ils se ramènent quasi toujours à un parcourt exhaustif d'une sous arborescence. Juste pour être sur qu'on parle de la meme chose tu peux me donner un exemple de complexité sous-exponentielle? (pas d'exemple de pb, juste un exemple de fonction de complexité)
@@PasseScience Bonjour, le problème d'isomorphisme de graphe (qui n'est pas connu pour être NP-Complet ni P), se résout en temps sous-exponentiel et même récemment a été trouvé un algo en temps quasi-polynomial ( O(exp(log(n)^cste) ). Ce qui est beaucoup, beaucoup mieux qu'un parcourt exhaustif.
fr.wikipedia.org/wiki/Problème_de_l'isomorphisme_de_graphes
Du coup imagine tu trouve une réduction polynomiale, d'un problème NP-Complet vers l'isomorphisme de graphe, on est bien.... ;)
@@librepenseur250 Tres intéressant cette classe GI, je ne l'avais encore jamais croisée. En effet pas mal d'espoir s'allume avec ce type de cas particulier. Il faudrait que je fouille un peu dans le papier de László Babai pour voir si l'algorithme quasi-poly est un algorithme utilisable en pratique et si on arrive à interpreter ce qu'il fait. Merci :)
@PasseScience bonsoir, j'ai sorti une vidéo sur la détermination d'un algorithme polynomiale pour le coloriage de graphe, j'ai fait une démonstration rigoureuse. J'espère que vous pourriez y getter un cou d'œil.
Bonjour, une démonstration formelle oui, rigoureuse on verra :). J'ai ajouté un premier commentaire question.
Voici le benchmark dont je parle dans mon commentaire sur votre chaine, il renvoie quoi votre algorithme sur les graphes donnés ? cedric.cnam.fr/~porumbed/graphs/
@@PasseScience Mais ce sont des graphes aléatoires ou ils sont toujours définis juste pour savoir, car s'ils le sont, j'aimerais pouvoir vous faire un algo qui génère puis qui résout en même temps. J'ai choisi de prendre C2000 et je reviens vers vous quand j'aurai fini de le coder, je le m'atterrais sur le drive.
@@resolution-de-probleme Je vous invite à faire une fonction qui lit les fichiers fournis par la page et les transforme en vos objets, pour automatiser la chose. Si j'ai bien compris ce sont des graphes pénibles pour les algorithmes de nombre chromatique. r1000.5 est plus intéressant.
@@resolution-de-probleme c2000 est un mauvais choix puisque l'objectif est de tester votre programme en comparant au résultat des autres et c2000 n'a pas de résultats dans le tableau... r1000.5 ou le450_25c sont plus intéressants.
Très bonne vidéo je m'abonne.
J'ai juste une petite question: À 9:24 sur l'illustration P est inclus dans NP ce qui veut dire que tout problème rapidement résoluble est rapidement vérifiable mais du coup la non inclusion et l'intersection simple est-elle possible. En clair existe-t-il des problèmes rapidement résoluble mais pas rapidement vérifiable. Je me suis posé cette question, désolé si elle est débile. En tous cas je vais me regarder toutes les autres vidéos et attendre impatiemment les suivantes ;)
Non, elle est pas débile. Formellement, NP est la classe des problèmes rapidement résolubles, mais de manière non déterministe, c'est à dire en s'autorisant de "deviner" des solutions. Ainsi, si un problème est dans NP, il est résoluble par un algorithme "rapide" qui "devine" la solution, puis qui vérifie que cette solution est bien solution. Mais si un problème est dans P, il est rapidement résoluble, donc il est à fortiori rapidement résoluble de manière non déterministe. Ainsi, on a l'inclusion P dans NP.
Je ne sais pas si j'ai été assez clair. La définition de NP dans la vidéo est bonne, et permet une meilleure compréhension. Mais je dois avouer que j'ai plus de mal à voir comment expliquer l'inclusion avec cette définition-là.
Merci pour cette explication, c'est un peu plus clair maintenant même si, je m'en doute, cela reste de la vulgarisation à mon niveau. Je suis très intrigué par les autres façons de définir P et NP. Je vais faire des petite recherches la-dessus. ;)
Merci beaucoup de votre explication claire! J’ai une question :
Vous donnez 3 exemples des problems NP : le problème de 3-coloration, le problème du sac à dos, le problème SAT.
En sens commun, on sait bien que NP et P sont différents, car au contraire à P, on n’a que des algorithmes exacts du type de la recherche par force brute en temps exponentiel, ou des algorithmes approchés en temps polynomial pour résoudre les problèmes NP.
Pourtant si un problème NP est défini comme un problème dont la solution peut être rapidement vérifiable, alors un problème P est aussi rapidement vérifiable.
Dans ce cas, comment peut cette propriété capturer la nature de NP qui est sensé être différent de P ?
Bonjour! merci pour votre intérêt dans cette vidéo. Je ne suis pas totalement certains d'avoir saisi votre question mais je pense que je vois.
En gros vous vous demandez comment on peut RIGOUREUSEMENT définir la classe NP et définir la classe P sans avoir à l'avance de critère pour séparer les deux notions. (et sans se reposer sur l'intuition qui ne donne pas de rigueur formelle)
Alors déjà, lorsqu'on rentre dans le cadre rigoureux, on n’étudie ici que les problèmes dit de "décision" c'est à dire formulé sous une forme ou la réponse est oui ou non.
par exemple "puis je colorier ce graphe avec 3 couleurs?" (plutôt que de demander comment le faire à l'algorithme). Parmi tous les problèmes de décision, on définit 2 ensembles:
Classe P: les problèmes tels qu'il existe un algorithme codable sur une machine de Turing universelle (Ça c'est la formalisation rigoureuse d'un ordinateur) répondant à la question en complexité polynomiale.
Classe NP: pour non-deterministic polynomial, qui en gros se demande s'il existe un algorithme finissant en temps polynomial sur une machine de Turing non déterministe.
C'est un peu subtile la définition rigoureuse de cette seconde chose mais, en gros, ça revient à doter la machine, d'une capacité de parallélisme infini, ce qui en forme vulgarisée revient à lui donner la possibilité de tester toutes les solutions en même temps. Donc on a bien 2 définitions rigoureuses, différentes, pour définir les deux classes, mais il se peut que ces définitions, bien que distincte, définissent un objet unique (si P=NP).
Ensuite il y a la classe NP-complet qui est une surprise: on peut démontrer qu'il existe parmi la classe NP des problèmes particuliers tels qu'on puisse y ramener n'importe quel autre
problème NP en temps polynomial. Ce n'est pas du tout évident au départ que la classe NP-complet n'est pas vide, c'est le Cook-Levin theorem qui donne le premier exemple de problème NP-complet.
Ensuite une fois qu'on a cet exemple, c'est beaucoup plus simple après pour démontrer que d'autres problèmes sont NP-complets, il suffit de montrer qu'on peut les transformer en cet exemple precis, ou en d'autres problèmes qu'on a déjà transformer dans cet exemple. (ça c'est ce que je fais dans la vidéo).
Ne pas hésiter à préciser votre question si je n'y ai pas répondu.
Merci beaucoup pour votre réponse rapide et patiente!
Oui, j’attends à une définition formelle de NP qui soit cohérente avec le sens en commun :
« Il n’y a pas d’autres voies qui s’offrent aux hommes, pour arriver à une connaissance certaine de la vérité, que l’intuition évidente et la déduction nécessaire ». - Descartes
Vous expliquez :
Classe NP: pour non-deterministic polynomial, qui en gros se demande s'il existe un algorithme finissant en temps polynomial sur une machine de Turing non déterministe. (Noter Définition 1)
Le problème est qu’ici, la « machine de Turing non-déterministe » n'existe pas dans notre monde physique à ce jour ! Comme vous dites « ça revient à doter la machine, d'une capacité de parallélisme infini, ce qui en forme vulgarisée revient à lui donner la possibilité de tester toutes les solutions en même temps ». En plus, cette « machine » fait référence à « Oracle » dans le théorème de Cook (voir son fameux article en 1971 ).
En fait, la définition informelle de NP (dont la solution peut être rapidement vérifiable) peut aussi être formalisée :
- NP est une classe des problèmes vérifiables en temps polynomial par une machine de Turing. (Noter Définition 2)
Il semble que ces deux définitions sont différentes de leur essence :
Définition 1 sépare NP de P, mais elle est basée sur la « machine de Turing non-déterministe » imaginaire, tandis que Définition 2 est basée sur la « machine de Turing » réelle, mais elle confond NP avec P.
En sens commun, bien que des différentes définitions d’un objet peuvent avoir le degré d'abstraction et le mode d’expression différente, mais elles devraient avoir la cohérence, c’est-à-dire, elles devraient désigner le même objet.
Donc, mes questions sont:
1. Y a-t-il un problème avec les définitions de NP ?
2. La définition de NP est-elle liée aux difficultés pour comprendre le problème P vs NP (dans votre vidéo, beaucoup de gens expriment ce sentiment) ?
@@PasseScience
@@yuli-ly7bd Bonjour, vous dites:
"Définition 1 sépare NP de P, mais elle est basée sur la « machine de Turing non-déterministe » imaginaire, tandis que Définition 2 est basée sur la « machine de Turing » réelle, mais elle confond NP avec P."
Déjà je pourrais revenir sur cette remarque parlant d'imaginaire qui est un peu douteuse car toutes les mathématiques sont des modèles abstraits, même le chiffre 1, et une machine de Turing déterministe est autant un modèle abstrait qu'une machine de Turing non déterministe.
Parler même de complexité algorithmique c'est par définition un comportement à l'infini et c'est donc aussi un modèle abstrait, etc... Mais c’était juste pour la remarque, je ne vais pas trop digresser sur le sens ou l'absence de sens à déclarer que certains modèles mathématiques sont réels et d'autres non.
Il y a ici plus court, pour réagir à votre paragraphe, il y a une confusion entre plusieurs choses.
-1) Le problème de décision dans son intégralité, exemple "trouver la procédure pour répondre, quelque soit le graphe, à la question se demandant si chaque graphe est 3-coloriable ou non" On est au niveau dans l'ensemble infini des instances possibles de notre problème et c'est à ce niveau la qu'on peut parler de complexité algorithmique.
-2) Se poser la question au niveau d'une instance de ce problème, c'est a dire ici pour un graphe donné. "Le graphe G est il 3-coloriable?"
-3) Se poser la question pour une instance donnée et un candidat solution donné. Exemple: "La 3-coloration suivante "C" est elle une 3-coloration valide pour le graphe G?" Et si on veut parler de complexité dans ce cas 3 on va raisonner sur l'ensemble des instances graphe+candidat-coloration possibles.
Et si on prend votre définition 2 pour NP, elle n'est en aucun cas la même que la définition de la classe P. Car elle ne porte pas sur le même niveau.
La classe P c'est l'ensemble des problème de décision qui peuvent être RÉSOLUS en temps polynomial (c'est à dire qu'on ne fourni à l'algorithme que l'instance du problème, ici un graphe G, et il doit répondre en temps polynomial à la question est il 3-coloriable)
La classe NP c'est l'ensemble des problèmes de décision qui peuvent être VÉRIFIÉS en temps polynomial. (et non résolus, c'est à dire qu'on fournit à l'algorithme une instance du problème, comme un graphe donné, ET un candidat solution. Le travail de l'algorithme est juste de se prononcer sur la validité du 3-coloriage fourni et non de conclure sur la 3-coloriabilite du graphe donné, qui pourrait être 3-coloriable d'une autre manière si le candidat coloriage ne convient pas).
Donc pour la classe P et la classe NP il y a bien une notion de complexité polynomiale dans les deux cas, mais pas pour réaliser la même chose.
Vous dite "Définition 1 sépare NP de P". Les définitions 1 et 2 sont mathématiquement équivalentes, donc si la définition semble "séparer" qq chose (ou qq soit votre conclusion a propos de la définition 1) alors la définition 2 fait la même chose. La définition 1 c'est une formulation en terme de RÉSOLUTION en temps polynomial sur une machine de Turing non déterministe, la définition 2 c'est une formulation en terme de VERIFIABILITE en temps polynomial sur une machine de Turing déterministe. Et comme je le présente ci dessus, ce n'est pas le même travail qui est qualifié de polynomial dans un cas comme dans l'autre.
C'est plus clair?
@@PasseScience Merci beaucoup de votre patience !
C’est vrai que le mot «imaginaire» que j’ai utilisé pour désigner cette NDTM (Non-Deterministic Turing Machine) “un peu subtile”, est susceptible d’avoir l’ambiguïté. En fait il existe en général trois interprétations de NDTM :
NDTM est une machine dotée d’une capacité de parallélisme infini ;
NDTM peut être simulé avec TM en temps exponentiel;
NDTM est une machine dotée de l’Oracle (dans le fameux article en 1971 de Cook).
Donc, ce serait mieux de mettre de côté « Définition 1 » basée sur cette subtile NDTM pour l’instant, et rester encore un peu sur « Définition 2 ».
En sens commun, NP et P sont différents, mais "Définition 2" dit : NP est une classe de problèmes vérifiables en temps polynomial par TM. Comme un problème P est également vérifiable en temps polynomial par TM, donc NP inclut P.
On remarque que, la relation entre NP et P est passée de l’« opposition » à la « inclusion ». C’est pour ça que je demande : y a-t-il un problème avec cette définition de NP ?
J’essaye d’expliquer ma question à travers une analogie :
Je connaissait le «vache», mais pas le «cheval». Un jour je voyait un troupeau de vaches et un troupeau de chevaux ensemble dans une herbe :
Yu demandait à Passe-Science : qu'est-ce que c’est ?
Passe-Science : c'est le cheval.
Yu : qu'est-ce qu'un cheval ?
Passe-Science : un cheval est un animal ayant une couleur.
Maintenant si vous me demandiez : tu sais ce que c’est un cheval ?
Je ne peux que répondre: je ne sais pas, car une vache est aussi un animal ayant une couleur.
@@yuli-ly7bd Ha mais je comprend mieux ou se trouve la confusion, c'est complètement admis que P soit inclus dans NP par définition. Et par construction ça a toujours été le cas, et ce quelque soit la définition.
Que ça soit selon la définition 1 ou la définition 2 P est inclus dans NP. Si un problème est P c'est trivial qu'il peut aussi être résolu en temps polynomial sur une machine de Turing non-déterministe (définition 1, et qu'il est donc aussi NP) et c'est aussi trivial qu'il est vérifiable en temps polynomial (définition 2, et est donc aussi dans NP). Il n'y a jamais eu "d'opposition" qq soit la définition, rien n'a jamais tenter de définir NP comme un ensemble disjoint de P, ça a toujours été une relation d'inclusion et ce qu'on cherche à savoir c'est si cette inclusion est stricte ou si c'est en fait une égalité, s'il existe le moindre élément dans NP qui ne soit pas dans P. Le cote disjoint ça serait plutôt pour la classe NP-complet, mais évidemment on en est pas certain (puisque c'est toute la question) NP-complet ce sont les problèmes qui sont dans NP et aussi en qq sorte "maximalement dur" ou "au moins aussi dur que". Si on a P différent
de NP alors on aurait bien disjonction entre P et NP-Complet. Voir la vidéo à partir de 9:35 je montre les inclusions avec des patatoïdes.
J'ai du mal à comprendre en quoi l'exemple du sac à dos est un problème NP complet:
s'il l'on prend le ratio ratio euro/kg minimal, que l'on sélectionne seulement les objets ayant ce ratio minimal et que l'on additionne leur prix, si ce prix est supérieur à notre prix voulu, le problème a une réponse positive façilement trouvable sinon non.
Aurais-je mal compris le l'énoncé du problème?
Hello, tu as sans doute saisi l’énoncé du problème mais sous estimé sa "mécanique". Prenons un exemple plus simple: imagine que tous les objets pèsent autant que leur prix (5euros = 5kg), le problème reviendrait à juste se demander si on peut faire rentrer plus de x kilos dans le sac sans dépasser le max autorisé. On peut encore simplifier en mettant notre objectif exactement égal à la capacité du sac. Et le problème devient:
Etant donné un ensemble d'entiers strictement positifs, est il possible d'en trouver un sous-ensemble dont la somme serait S ? (un entier objectif donné). Par exemple:
-y a t il un sous ensemble de {1,2,5} dont la somme est 7? et la réponse est oui 2+5.
-y a t il un sous ensemble de {1,2,5} dont la somme est 4? et la réponse est non.
Donc pour cette version très simplifiée, ce cas très particulier du problème ou tout tes ratios sont égaux et ou on vise une somme exacte donnée, comment tu t'y prendrais pour donner une réponse rapide à la question? quel serait ton algorithme?
Sciences étonnantes a fait une vidéo sur le sujet, récemment ;)
Les meilleurs algo pour la coloration de graphe par exemple ? C'est quoi ? e^n ? Tu as des liens qui explique l'algo ? Je serais curieux de comprendre ce qui le rend si compliqué que ça a résoudre !
Ca sera en a*b^n oui avec a,b des constantes plus ou moins grandes en fonction de l'algo. Ce qui rend difficile l'algo, comme dans tous les autres pb NP-complet c'est le caractère non local de tes décisions, c'est a dire que décider de colorier un nœud d'une couleur peut te forcer à en colorier 30autres d'une certaine couleur, puis reprendre une décision va t'en faire colorier 30autres, et la tu va te rendre compte que le dernier des 30 est incompatible avec un des nœud déjà colorié du coup tu va devoir tenter autre chose, et le problème c'est qu'on ne sait pas faire autrement que "tenter". On va éliminer tous les cas "locaux" ou on sera sur que ce n'est pas possible ou sur que ca "change rien" mais il va rester des trucs dans le genre ou une décision peut se rependre dans le problème et n'avoir des conséquences que tard, qu'on ne sait pas prévoir autrement qu'en essayant.
En pratique, on utilise plutôt des heuristiques qui sont des algorithmes qui fournissent toujours des solutions mais pas forcément des solutions optimales : des coloriages à quatre couleurs quand trois peuvent suffire par exemple.
Si ça t'intéresse, tu peux regarder du côté de DSATUR entre autres :)
Salut, excuse moi de poser une question stupide mais je ne comprends pas comment on pourrait démontrer que NP implique P parce que si tu as P il est facile de vérifier NP mais comment tu peux vérifier un problème facile à vérifier s'il n'a même pas été résolu?
C'est là tout le principe du problème 🤷🏿♂️
@@mistereasy59 ah merci, il me semblait bien que c'était un énorme problème, d'ailleurs il y a plusieurs chose que nous avons du mal à imaginer que nous puission un jour démontrer, alors pourquoi ne pas en faire une loi? Sans doute, parce que pour les mathématiciens ainsi que pour ma part c'est assez frustrant de juste admettre une égalité...
Hello @JeSuisTonPierre, je ne suis pas sur d'avoir saisi la question alors je l’interpréte de deux manières tu choisis: tu demandes comment on a réussi à démontrer qu'un problème NP (non deterministic polynomial) était P (polynomial) ? réponse: on a jamais réussi à faire une telle chose, c'est comme le dit @mistereasy59 tout le cœur du problème, on ne sait pas à l'heure actuelle si P=NP ou P différent de NP. On a jamais réussi à démontrer P=NP mais on a jamais réussi à démontrer le contraire non plus. L'avis général c'est qu'il semble plus probable que P soit différent de NP. Autre interprétation de la question: tu demandes à quoi pourrais ressembler une preuve que P = NP, ie l'allure que ça pourrait avoir? he bien l'allure la plus simple consiste à juste trouver une manière alternative de résoudre un problème NP-complet en temps polynomial. Si pour un problème NP-Complet qcq on trouve une manière complètement différente de l'aborder et qui en trouve la solution en temps polynomial alors on saura que ce problème NP-complet est dans la classe P. Et la propriété magique du domaine c'est que si pour un seul problème NP-complet on trouve une preuve qu'il se trouve dans P alors tous les autres problème NP-Complet seront également dans ce cas.
Bien pour rentrer un peu d'intuition avant l'exam
bonjour je voudrais savoir suite à l'écoute attentive de ta vidéo si un simple problème qui consiste à trouver l'écriture d'un problème en terme équationnel rentrait dans la catégorie sac à dos des problème np complet? par exemple ''un père dit à son fils lorsque j'avais l'âge que tu as maintenant j'avais le triple de l'âge que tu avais , sachant que le père a actuellement 60 ans quel âge a actuellement son fils" je crois qu'une fois que l'on a réussit à réécrire le problème sous forme d'équation il est plus facile à résoudre mais je pense également qu'il est extrêmement facile à vérifier une fois en possession de la bonne équation.à ceux qui veulent trouver la réponse à cette énigme de mon cru je ne spoilerais pas ^^ si quelqu'un me réponds la bonne réponse j'irais juste confirmer ou non mais surtout la beauté de ce problème réside dans sa méthode de résolution... n'y allez pas à taton quoi
Traduire le problème en équation est avant tout un problème de linguistique et de sémantique. Donc c'est autre chose :) C'est une énigme rigolote qui a beaucoup de variations. Ton probleme rentre dans la categorie des systemes d'equations lineraires à N inconnues, et cela se resoud en temps polynomiale. Certes verifier une solution du systemes d'equations est plus rapide que d'en trouver une mais les deux taches (verifier ou trouver) reste ici dans la meme famille de complexite (la famille polynomiale) et dans le cadre de notre question P vs NP elles sont vues comme "aussi dures" l'une que l'autre (principalement parcequ'on les compares à des choses enormes).
Guillaume le cam votre solution pourra fonctionner à mon avi pour le pb n2, si on calcul le rapport poid dollard de chaque objet il suffit de prendre les objets avec le rapport le plus elevé
Merci bcp pour la vidéo.
Sinon, quelqu’un peut me dire si ma compréhension est bonne: si on arrive à résoudre un problème NP complet alors on a résolu l’équation P=NP
Hello, oui c'est ça, si tu arrives de trouver un algorithme que tu puisses démontrer polynomial pour un seul des problèmes NP-complets alors tu resouds la conjecture par l'affirmative, ça démontrerait que P=NP.
Vous avez très bien construit votre vidéo, c'est clair !
J'ai juste un peux de mal au niveau du temps polynomial: comment la constante est déterminée ?
Tu veux dire comment on sait qu'un algorithme donné fini en temps polynomial?Je vais prendre un algorithme pour trier un tableau comme exemple: il existe plein de méthodes, l'une des plus mauvaise est la suivante: L'algorithme parcourt tout le tableau, cherche le maximum, le met en première position, et recommence exactement la même chose avec la suite du tableau (le re-parcourt, cherche le maximum et le met donc en 2eme position etc...) Au final cet algorithme va bien trier le tableau et il lui faut faire environ N+(N-1)+(N-2)+(N-3) etc... opérations
(Parce que le premier coup il va parcourir les N éléments du tableau, puis un de moins etc). C''est la somme des entiers de 1 à N, cette somme vaut N(N+1)/2. Sous forme développée ca fait donc environ N^2/2 + N/2 opérations c'est bien un polynôme, cet algorithme de trie fait donc son travail en temps polynomial.
Ça répond à la question?
+Passe-Science Oui merci pour la réponse ! C'est plus clair pour le temps polynomial.
Mais en ce qui concerne le temps exponentiel ; par exemple avec le problème des noeuds, un algorithme qui crée toute les possibilités de mises en couleur, son temps sera calculé comment ? N le nombre de noeuds (et constante le nombre de couleurs ?)
Oui, pour un algorithme qui testerait tous les coloriages on voit que le nombre d’opérations nécessaire sera grossomodo le nombre de coloriages possibles. S'il y a N nœuds et K couleurs il y a K^N coloriages possibles. (Ce n'est pas un polynôme en N, c'est bien exponentiel ici). Dans la vidéo je parle de "temps" car c'est plus abordable, en pratique on préfère parler de nombre d’opérations.
Merci beaucoup pour ces précisions !
j'en connais un encore plus mauvais:
1- vérifier si le tableau est trié
2- réordonner les valeurs du tableau aléatoirement
3- recommencer
:)
Superb vidéo, comptes-tu faire d'autre vidéo sur les autres types de problème, tel que SUBEXP, etc, ?
Merci pour les encouragements. Oui peut être un jour je parlerais des autres classes de complexité mais a priori pas avant longtemps car c'est moins une question fondamentale :)
Passe-Science Merci pour ta réponse rapide!
Il y a un truc qui me chiffonne : Un problème est NP-complet si on peut convertir n'importe quel problème en celui là. Mais vu que tous les problèmes NP ne sont pas NP-complet, ça implique que pouvoir transformer le problème A en le problème B ne signifie pas qu'on peut transformer le problème B en le problème A
Dans ce cas, autant je comprend que s'il existe un problème P qui soit NP-complet, alors tous les problèmes sont P car on peut les transformer en celui-là, que je ne vois pas du tout en quoi ça les rend tous NP-complets
PS : T'es sous-côté ^^
Hello pour le premier paragraphe oui tout à fait, tu peux voir un pb comme un ensemble d’énoncés et les pb NP-complet sont "suffisamment gros" pour qu'on puisse mapper n'importe quel ensemble issue d'un autre pb NP dessus. Un NP qui ne serait pas NP complet ne permettrait pas de trouver un mapping surjectif. (je suis pas super clair j’espère que c'est suffisant pour intuiter ce que je veux dire). Pour ton 2eme paragraphe, très bonne question et je m’étais posé la même à l’époque de la vidéo alors je te donne des éléments de réponse car je n'ai pas refermé ce dossier encore proprement. En fait déjà dans ma vidéo, je parle pas vraiment des classes NP NPC et P, je parle des classes FNP FNPC et FP en gros dans ma vidéo les pb sont des pb ou la solution est complexe, doit être décrite, on cherche des programmes qui ont comme output un truc riche. Alors que les pb de décisions c'est la version ou on force l'output du programme à être juste OUI ou NON. du genre plutôt que de se demander comment tri colorier un graphe, on se demande peut on le tri colorier. (et le programme doit juste dire oui ou non). Donc toi tu te trouver dans le cas ou NPC est dans E avec E = P = NP et tu te demandes pourquoi un truc qcq dedans aurait le pouvoir de pouvoir représenter n'importe quel autre problème, la réponse est en fait une arnaque: comme résoudre un problème qcq dans NP est maintenant faisable en temps polynomial, alors, pour le réduire en un autre de ton choix, tu peux commencer par le résoudre, une fois que tu l'as résolu et que tu sais donc si ton programme doit répondre oui ou non et ensuite tu peux mapper ton énoncé de force sur 2 cas particuliers du problème en lequel tu veux le réduire, un pour oui et un pour non. Donc en gros ta réduction est en fait une résolution suivit d'une réduction débile, comme la premiere se fait maintenant en temps poly tu as bien au total une réduction en temps poly.
Mais clairement ici on a l'impression qu'on a perdu un truc plus subtile et a l'heure actuelle je ne sais pas si c'est possible de décrire le truc plus subtile auquel tu penses (et auquel je pense) ou on aurait une réduction qui a bien un sens, qui préserverait la structure, et si c'est possible je ne sais pas comment. Mon instinct en fait me dit pour le moment, que la possibilité de cette arnaque, rend impossible de definir proprement la "reduction" au sens ou on aimerait pouvoir la définir.
Bonjour,
Excellente vidéo pourrais tu me donner la referenxe de ton livre sur la Physique quantique en haut de ton etagere ?
Hello, il y en a deux:
Le premier est assez "simpliste" et peu dense, et quelque fois dans de rares passages pas totalement maîtrisé:
www.amazon.fr/Physique-Quantique-enfin-expliqu%C3%A9e-simplement/dp/2953966315
Le deuxième est abordé de manière historique très riches en plus de la vulgarisation en soit, ça reconstitue le cheminement intellectuel j'ai beaucoup aimé:
www.amazon.fr/Mod%C3%A8le-Standard-Physique-Particules-l%C3%89lectron/dp/2729880011
Passe-Science Merci beaucoup pour cette réponse rapide 😁
J'ai résolu un des problèmes mais l'institut ne répond pas à ma publication
Le plus sage est de commencer plus modestement par des forums de maths pour exposer vos idées.
@@PasseScience a ok merci , par exemple lequel
Merci !
Éternal Golden Braid ?
Oui il y a le GEB qui traine :)
lorsque l'humain examine le problème il peux faire quelque chose que ne peux pas faire la machine c'est à dire regarder le problème dans sa globalité sans prendre les étapes une par une. Par exemple un ordinateur va observer des détails sur un visage pour le reconnaître tandis que nous en avons une vision globale avec donc logiquement une quantité infinie de détails. si on pouvait transférer cette intelligence globale à un ordinateur (peut etre avec un ordi quantique qui traite une infinité de donné a la fois).
Nous ne sommes que des machines, élégantes et évoluées, mais des machines tout de meme. Ce qu'on peut faire rien empêche un ordinateur de le faire, c'est une question de programmes. La vision "globale" que tu cites c'est un mauvais exemple car on fonction vraiment de la meme manière qu'un ordinateur pour le coup :) le deep learning ca fait par principe un truc vraiment très proche, nous aussi on dispose de couche de neurones qui filtre localement les details et les passent aux couches suivantes, l'impression de "globalité" dans notre traitement des choses n'ai lié qu'au fait que seul ce qui se passe dans les dernières couches ne soit interpretable par notre conscience. J'ai beaucoup suivi les péripéties du programme de deepmind alphago qui a historiquement battu pour la premiere fois un humain top niveau au go, et en tant que joueur en dan, je peux dire que ce que fait la machine est très proche de ce que nous humain faisons, et que s'il excelle dans un point c'est dans sa vision globale de la position, qui depasse maintenant la notre. Il y a encore une infinité de chose qu'un programme ne peut pas faire (c'est pas demain qu'un programme inventera un nouveau Alphago, il nous faut encore des humains pour inventer cela) mais il n'y a pas d'obstacles fondamentauxx :) On peut se demander ce qu'il se passera lorsque ca arrivera !
Passe-Science je suis d'accord sur le fait que nous fonctionons comme un ordinateur mais je pense qu'il y a une nette différence entre lui et nous c'est que nous humain sommes branché à "l'univers" comme si nous avions une connexion wifi avec l'infini que l'ordinateur ne possède pas car fabriqué par un être humain qui n'a pas conscience de sa connexion. (impossibilité de mentaliser l'infini) (oui je sais c'est carrément théorique et non scientifique mais je vois les choses comme ça)
pour moi il n y a pas de lien entre le fait qu un probleme soit rapidement verifiable et qu il soit rapidement soluble , je m explique si je connais le code secret d un cadenas a 10 chiffres (rapidement verifiable) je ne vois en quoi cela va m aider a demontrer comment deviner ce code..
Hello, l'analogie est intéressante mais la "différence" avec un problème mathématique donné c'est que dans le cas du cadenas il y a des règles du jeu assez claires "tu ne peux pas regarder dedans" (sinon très probablement déduire la combinaison est assez facile). Dans un problème mathématique, tu as tous les droits, tu peux t'y prendre comme tu veux, ce que l’énoncé du problème te donne comme information rapidement accessible est bien moins évident. D'autre part, dans le cadre de cette question P vs NP, on colle dans le même panier des choses qui sont pourtant très différentes: des temps "polynomiaux". C' est à dire que dans cette question on considère comme "aussi dur" résoudre un problème en temps linéaire (proportionnellement à la taille de l’énonce) et résoudre un problème en temps quadratique par exemple (proportionnellement à la taille du carré de l’énonce), c'est à dire que ça accepte que résoudre soit beaucoup plus long que vérifier, mais que ça reste dans la même "classe de complexité", en gros ce qui nous intéresse en résumé et qui n'est pas évident par rapport à l'exemple du cadenas c'est: peut on, en s'autorisant tout ce qu'on veut, trouver la solution d'un problème rapidement vérifiable d'une manière fondamentalement plus efficace que de tester toutes les combinaisons une par une (même si ça reste beaucoup plus long que de la vérifier). Et c'est cette question qui est encore irrésolue.
TheAmazeer si tu devinait ses codes, alors tu peu tout ouvrir, c'est ça la subtilité.
Bonjour j'ai réussi à reprondre a la question p=np comment faire pour récupérer la récompense
Ecrire rigoureusement la démonstration, la faire relire, la publier. Et le reste suivra
Oui mais à qui dois je l'envoyer merci de l'aide
@@resolution-de-probleme Le problème avec ce genre de sujet, c'est qu'il y a de tres forte chance, que votre tentative soit "naïve" et des tentatives de démonstrations naïves e-mailée à des mathématiciens il y en a vraiment beaucoup. C'est pour ça que le plus important, pour avoir une suite, ça sera d’être modeste dans la forme, ne pas arriver en prétendant avoir la solution, mais plutôt demander d'en débattre ou de chercher ce qui n’irait pas dans l'approche etc... Meme si vous aviez le bon destinataire, si vous faite défaut dans la forme ça ira directement à la poubelle. Déjà ce que vous pensez avoir montré c'est dans quel sens de la conjecture? votre conclusion c'est P=NP ou P différent de NP? Je peux déjà faire une première passe ici, même sans vous risquer à donner des détails révélateurs, je peux juste regarder vaguement la structure global avec qq question pour voir à quel point c'est "crédible". Donc c'est P=NP votre conclusion ou le contraire?
Oui ma conclusion c'est p=np
Juste pour être sûr il faut juste connaitre le nombre de couleur possibles c'est bien ça
Donc, si j'ai bien compris le problème du coloriage c'est le même que celui du sac a dos? ou alors C'est juste que les 2 sont transposables en problème SAT? Car j'arrive pas a faire le lien sinon.
Tout à fait ces 3 la sont NP complets (et il y en a beaucoup d'autres) donc par définition tu peux transposer n'importe quel problème NP (pas forcement NP complet) en chacun de ceux ci. Ce qui implique de pouvoir passer de un de ses 3 la à n'importe lequel des deux autres, et donc que oui 3-coloriage et sac à dos sont le même problème. Les transposition ne sont pas toujours triviales :)
Ah oué... ben merci d'avoir répondu déjà c'est super cool de ta part ;)
Mais sinon le lien entre le problème du sac et du coloriage j'arrive pas a le faire perso. Peut-être en associant des couleurs au objets ? et encore O_o
Alors a priori en cherchant vite fait sur le web tu as ceci:
staff.ustc.edu.cn/~csli/graduate/algorithms/book6/947_a.gif
Chaque étiquette ramène à un problème NP-complet connu, et ceci represente des equivalences qui ont ete demontrees. Ie on peut transformer SAT and 3-CNF-SAT qui peut lui meme etre transformé en clique problem qui peut etre lui meme transformé en etc... puis en subset sum problem. Et ailleurs sur le web j'ai trouvé que tu peux transformer subset sum en sac à dos. Ce qui prouve la NP-completude de tout ce petit monde en admettant que CIRCUIT-SAT est NP - complet ce qui se demontre autrement. Donc sac à dos est NP-complet et peut donc représenter n'importe quoi d'autre avec, apres peut etre pas de maniere triviale si on a eu besoin d'autant d'etapes intermediaires ca peut donner une transformation velue.
Donc, si je comprends bien, on ne peut pas faire de transformation directe entre le problème 3-coloriage et du sac a dos, MAIS on peut les transposer en un autre problème commun ? probablement en problème abstrait comme le SAT (enfin, il l'est pour moi XD)
Passionnant sinon. Complexe, mais passionnant ;)
Au niveau des transformations, méfie toi elles sont orientées. Lorsque tu transformes, comme on l'a fait dans la vidéo, SAT en un problème de 3 coloriage, tu démontres que un 3-coloriage est au moins aussi difficile que SAT et peut représenter au moins autant de problèmes que SAT. (parce que si tu sais résoudre 3-Col cette transformation, de SAT vers 3-Col, peut t'aider à résoudre SAT, mais si tu sais résoudre SAT cette transformation seule ne t'aide pas à résoudre 3-Col) La transformation en elle même ne te montre pas d’équivalence.
Mais le truc subtile c'est qu'on dispose d'un probleme NP-complet on va dire "Racine" pour lequel
on sait démontrer qu'il peut modéliser tous les autres. Donc en pratique tu peux te retrouver avec:
(N'importe quel NP) -> Racine -> SAT -> 3 color -> Bob -> machin -> truc.
Et donc après il est possible que la seul transformation dont on dispose pour passer de machin à 3-col soit:
Machin ->Racine(par defintion) -> SAT -> 3 color.
Rien empêche évidemment de trouver des transformations plus directes des raccourcis, mais c'est vrai que vu la tete des problèmes sac à dos et 3 color ça ne se ressemble pas, et pourtant c'est bien le même. :)
À mi-chemin... pour le reste, merci.
en gros ça veut dire que si P=NP je peux pirater tous les sites internet du monde :)
ben oui si le problème SAT peut être résolu en tps polynomial, alors cela ne marche pas que pour les équations logiques simples... mais aussi pour les formules plus complexes
comme trouver l'antécédent d'une fonction (avec des nombres entiers sous une valeur de 2^x, division donne nombre entier seulement)
Oui et non, car la complexite theorique ne renseigne que tres peu sur le temps pratique. Par exemple peut etre quil existe un algorithme en temps polynomial de la taille (et que du coup P=NP) qui conclut en un temps T=A*N^k (T le temps et N la taille de l'input) mais avec un A tres gros et un k tres gros, genre polynomiale de degré 1089 (k=1089) ce qui ne sert en pratique a rien du tout. Et ce qui est drole cest que j'ai souvenir d'avoir vu des exemples de problemes industriels pour lesquels ont a des solutions polynomiale mais qui en pratique sont beaucoup plus lente a etre trouve qu'avec l'algorithme exponentiel. (justement a cause de truc dans ce genre la, de grosse constante ou gros k)
Ayant beaucoup réfléchi au problème NP=P. Que j'ai instinctivement mis en lien avec l'interprétation de Hugh Everett du chat de Schrödinger , la Théorie du Chaos, Principe de Church-Turing-Deutsch. J'ai trouvé une voie où je penses que c'est possible. En introduisant la notion d'anti-hasard. Je m'explique.
Si prend l'interprétation de Hugh Everett du chat de Schrödinger, notre univers ce scinderait en 2 à chaque choix possibles.
Soit notre univers, celui où on vit comme Univers 0 à un temps de Planck donné. Celui donnerait naissance a une infinité d'univers parallèle.
Prenons maintenant l'ensemble des univers crée de l'univers 0 et l'ensemble des univers crée par ceux là.
Si on se place de notre point de vue nous pouvons voir qu'un seul chemin, qu'une suite de calcul possible. On pourrait comparer notre univers à une machine de Turing déterministe on a une transition possible. Par rapport a notre référentiel.
Si maintenant on observe l'ensemble des univers dont l'univers 0, nous sommes dans le cas d'une machine de Turing Non déterministe, Chaque univers est une suite de calcul avec plusieurs transitions possibles.
Cependant l'absurdité viens là, un tel ensemble d'univers où finalement tout se produit est déterministe.
Donc de ce référentiel NP=P, car le non-déterministe extrême pousse au déterministe.
Autrement dit la question ne serait pas de trouver une solution car on sait qu'elle existe mais pouvoir trouver la branche. Autrement dit La solution et la vérification s'équivalent dans cette infinité.
NP=P si tout les choix peuvent être vérifié simultanément à la manière de l'ensemble de l'univers. Si le nombre de possibilité de vérification croit plus vite que le nombre de possibilité a vérifier.
Hello, je ne suis pas sur de tout suivre, mais je reviens sur quelques définitions/utilisation des termes. Dans l’interprétation de Hugh Everett c'est le monde subjectif qui est non-déterministe, ie étant donné ou on se trouve et ne sachant que cela (de notre point de vue) on ne sait pas ou notre branche va continuer. L'univers lui, en considérant toutes les branches est déterministe (ce sur quoi tu retombes lorsque tu dis "Cependant l'absurdité viens là"). Ça sera ainsi qu'on utilisera ces termes (pas dans le sens inverse), par exemple la mesure (en physique quantique) est subjectivement indéterministe (on, ne peut, nous, jusqu’à preuve du contraire, pas prédire son résultat), en revanche, la fonction d'onde (qui contient en elle toute les possibilités de résultats de mesure) est déterministe (elle a une évolution unique entièrement déterminée par l’équation de Schrödinger). Ensuite la question P=NP est une question mathématique, ce n'est pas une question physique. Pour le voir il suffit de remplacer le mot "Non-deterministic" par "infiniment parallèle". La question est de savoir, si un certains types de calculs qu'on peut résoudre en temps polynomial avec une capacité de calculs infiniment parallèle (autant d'ordinateurs qu'on veut), peut être également résolu sur un seul ordinateur (sans parallélisation) et également en temps polynomial. Lorsque tu dis "Donc de ce référentiel NP=P" par exemple, je ne suis pas sur que la notion soit maîtrisée/comprise.
Effectivement je partais du postulat que nombre d(ordinateurs/univers) est infini. Quand je dis dans ce référentiel NP=P. C'est plus que maladroit , ce que je voulais dire par c e "référentiel" c'est un référentiel où l'ont a accès aux donnés de toutes les branches, ainsi pour trouver une solution il suffisait de vérifier. En tout cas grâce a votre réponse je peux voir mes erreurs merci beaucoup.
Excellent...si seulment tu été mon prof :D
Assume p is the fastest solution to my question And Np is the set of solutions that can solve the problem Then p = Np in one solution And p differs from Np in the remaining solutions. The correct answer can be checked But these same answers cannot be calculated quickly
Ah... Premier à commenter ! En plus je l'attendais vraiment le problème P=NP !
Mais pourquoi P = NP est à 1 million $ ? Je veux, dire. Si on résoudait l'hypotèse de Riemann, on aurait la réponse aux nombres premiers, ce qui ouvrirait plein de porte aux mathématique! Mais P = NP, si on le résoud, toit ce que ça fera, c'est le résoudre. Ça ne sert pas à grand chose de savoir si P = NP.
Ça a plein de conséquences sur la compréhension de l'algorithmique, et plein de conséquences potentiellement pratiques sur le cryptage ou sur la résolution de problèmes.
@@PasseScience Ooooooh Ok merci
Si P=NP, alors toute la cryptographie asymétrique actuelle s'écroule. En effet, elle est basée sur la notion de fonction à sens unique, c'est-à-dire une fonction dont le calcul d'un image se fait en temps polynomial, mais dont le calcul d'un antécédent se fait en temps exponentiel.
P=NP P-NP=0 P(1-N)=0 d'où P=NP ssi N=1 ou P=0 CQFD c'est où qui faut aller chercher le million ? hihihi
Mdr
J'ai compris 2% de ce que tu as dit , ça veut dire quoi en français sans les math ?
niveau collège (et "ssi" = si et seulement si)
Laz med je te vole ta démonstration je part avec le fric...
Chercher pas comprendre il a ecrit nimp
0:55 pour moi ça signifie évidemment que P≠NP ! J'ai mis 10 mois pour formaliser le paradoxe de Banach-Tarski (c'est long), mais mon logiciel assistant de preuve la vérifie en 4 minutes (c'est rapide). J'ai l'air de plaisanter mais c'est pourtant ce qui est dit ici. Et donc, je ne comprends pas en quoi la question de P=NP ou P≠NP est pertinente en soi. Mes collègues s'énervent à essayer de m'expliquer et moi je m'énerve à leur expliquer que ce problème m'est totalement incompréhensible.
Hello, ce qui est dit à 0:55 est "en gros" ce de quoi la question parle, mais lorsqu'on parle vraiment de la conjecture P vs NP on ne parle pas que de cette version "en gros" mais bien de quelque chose de tres precis mathematiquement. Si on reste dans les formulations "en gros" du problème il y en a une autre qui est interessante: "dire que P different de NP ça revient à dire que dans pas mal de problèmes, pour savoir si une solution existe, on a rien de plus intelligent que de tester 1 par 1 la "majorité" des candidats possibles." Par exemple dans le cas d'un graphe et ou la question serait "est il tricoloriable?" (voir vidéo) he bien meme sil y a des astuces algorithmiques, à la fin on semble avoir besoin de tester un nombre exponentiel de cas juste en les énumérant bêtement. C'est ca dans l'essence la question adressée derrière la conjecture, y a t il, dans un sens mathématique précis, mieux que d’énumérer et tester betement une par une la "majorite"(toujours selon un sens mathematique precis) des candidats pour savoir si l'un d'entre eux est solution du probleme? Dire que P different de NP c'est penser qu'il n' y a rien de mieux que cela, dire que P = NP c'est penser qu'il y a mieux. Mais on a jamais reussi à trouver mieux, et jamais réussi à demontrer que "mieux que cette enumération bete" n'existe pas. Voila voila.
@@PasseScience : ça veut dire que si on arrive à écrire un algorithme qui résout le problème du graphe aux trois couleurs en une complexité polynomiale, on aura montré que P=NP ? Et que si on démontre que quel que soit l'algorithme de ce problème précis, on trouve toujours des exemples de graphes qui se résoudront en un temps exponentiel (genre la diagonale de Cantor qui montre que quelle que soit l'énumération des réels, il s'en trouvera toujours un qui ne pourra pas y être), on aura prouvé que P≠NP ?
@@j9dz2sf roglo Oui tout à fait (en theorie c'est expliqué dans la video). Il suffit de le faire pour un seul des problemes dit NP-complets et oui le 3 coloriages de graphe en est bien un (la notion est egalement abordée dans la video ainsi que la raison pour laquelle le faire pour un implique que c'est valide pour tous). Voila voila.
@@PasseScience : du coup, je trouve que ça aurait été mieux si on avait appelé ça "problème du coloriage d'un graphe en 3 couleurs" plutôt que "P=NP" qui me parait peu parlant et très abstrait. Parce que le résoudre résout au moins quelque chose. Tandis que sous la forme "P=NP", on voit pas bien ce que ça résout. Même si c'est équivalent.
Très bonne vidéo. Par contre en tant que professionnel de l’informatique je dois dire que tant P = rapide est une notion de Math et pas d’info. En pratique O(n^2) c’est déjà lent et tous ce qui a un exposant supérieur à 2 est inutilisable pour des données non trivial. Il y aura forcément quelqu’un pour dire oui mai si le facteur est suffisamment petit… Ça veut simplement dire qu’il considère une taille de problème qui est très limité et donc des données triviales.
Une autre façon de parler de l'hypothèse du continu. ;-)
il aurait été fort utile de définir la notion de d'algorithme déterministe et non déterministe et de NP-difficile ----difficulté par rapport à une classe
C'est marrant je ne sait pas comment l'expliquer mais j'ai l'impression que le problème parle de lui-même, du genre si on galère à trouver la réponse à P vs NP c'est visiblement une question complexe ou il faut voir plein de possibilités et ça ressemble à P n'est pas égale à NP du coup reste plus qu'à le démontrer, mais on va galérer, ce qui semble être le cas vu qu'on ne l'a toujours pas trouvé.
Après je dis probablement des bêtises puisque je ne suis pas sûre d'avoir compris le problème
Bonne video mais quand ça parle de NP complet avec l'exemple je trouve sa un peu compliqué à mon gout faut aller plus doucement et simplifier au maximum cet exemple
❤👍❤️
Salut, essaye de faire des vidéo de 40 min ou tu explique vraiment en détail un problème donné. Genre les outils mathematique pour le résoudre et de quelle manière de faire. Comme ça on comprendra vraiment la difficulté d'un problème.
Très bonne vidéo, avec plein de points intéressants, mais cependant je pense qu'on peut apporter une petite nuance entre les aspects théoriques et pratiques... En fait, l'archétype du problème NP-complet, c'est plutôt le problème SAT, et c'est vraiment un problème très étudié, beaucoup de gens ont élaboré des techniques de réduction redoutablement efficace, ce qui permet de programmer des solveurs SAT très rapides en pratique sur la majorité des cas. A l'inverse, pour beaucoup de problèmes polynomiaux, la fameuse constante qui se trouve devant l'exposant peut être tellement grand que le programme sera en pratique complètement inutilisable et échouera lamentablement sur des petits cas. La complexité nous dit que ultimement pour des très grandes valeurs d'entrée, SAT sera forcément plus long en moyenne, mais il s'agit surtout d'une notion théorique, et les algorithmes utilises en pratique ne correspondent en général pas aux optimaux théoriques... Mais ça demanderai sûrement une autre vidéo d'explications :)
Tout à fait il y a beaucoup de matière autour de ce genre de discussion pour continuer la vidéo :).
02 23 : Temps = taille puissance constante.
P = NP
Algorithme du cavalier :
On divise un échiquier de 64 cases en carrés de 4 cases.
On place ensuite le cavalier à une extrémité d'un bord puis, il s'agit d'appliquer la suite :
(12+0) +(12+1) +(12+0) +(12+1)...
+0: on saute un carré de 4 cases.
+1: on saute vers le carré plus haut vers le centre le plus proche en suivant l'ordre horaire.
Si on a comme postulat de départ que le cavalier n'a pour seules
possibilités son déplacement en L, et qu'on doit suivre le mouvement
horaire, on n'a par défaut qu'une possibilité par mouvement (mis à part
quand il y a +0, ou +1, mais alors, le décalage reprend cette possibilité de mouvement).
Si on suit un mouvement chronologique
horaire, on arrive naturellement, grâce à l'algorithme, à la case 64
sans avoir recoupé une des cases.
Donc, dans ce cas, P=NP.
Hein ?
@@PasseScience Dans le cas du problème du cavalier, on peut résoudre le problème en appliquant un algorithme, donc P =NP.
@@benjaminmoine588 Hum, je ne suis pas sur que la notion de classe P, classe NP et que le sens de P = NP soit maitrisé ici :)
@@PasseScience Sûr. Ne soiENT maîtrisés.
Ah bon, et pourquoi cette interrogation prématurée?
@@benjaminmoine588 Qu'est ce que la classe P pour vous?
La question qu'on serait en droit de se poser après une vidéo aussi difficile est: Faites-vous des sports de combats ? (je dis ça à cause des bras et du nez) Et si oui, pensez-vous faire une vidéo avec Scilabus ?
Et très bonne vidéo, comme d'hab!
Haha:) , je suis censé laisser mon numéro la non? :P pas de sport de combat, mais une sorte de "street workout" de l'escalade (en salle) et beaucoup d'autres trucs!
+Passe-Science Ho cool ! Ca serait bien une vidéo avec Scilabus sur l escalade, avec comme sujet les énergies (pesanteur, cinétique), l'adhérence sur les prises etc.
Ca pourrait être sympa de voir ce sport d un point de vue scientifique !
sinon dans le problèe de type sat tu pars du principe que le ou suppose d'avoir 2 éléments distinct et même ici parfaitement opposé, mais pourquoi ce présupposé? certe il remettrait en cause le problème mais on peut aisément imaginé que le ou soit placé entre 2 vrai représentés par des élements distinct à moins que la définition du ou en mathématique ne soit par soucis pratique plus restrictive qu'à l'accoutumé en français ce qui est surement le cas si comme tu l'as fais tu n'as pas pris le temps de l'expliquer.
Hum je ne suis pas sur de te suivre. Le "ou" mathématique c'est un opérateur logique qui combine deux variables booléennes, c'est à dire deux variables qui peuvent valoir chacune "vrai" ou "faux". Et la manière dont le ou combine ces variables c'est qu'il produit "vrai" si une des deux variables ou les deux valent "vrai" et qu'il produit "faux" si les deux variables sont à "faux". Ça répond à ta question?
mince je crois que je suis encore un peu plus embrouillé je crois que je vais reformulé (dsl je manque beaucoup de clarté dans mon propos :s) en gros (ce que je comprends du problème sat mais ptet que je me trompe) :
(a ou b) et (c ou (non a)) soit a b et c doivent prendre les valeur vrai ou faux . Déjà je ne comprends pas pourquoi on peut transformer ce problème en un problème à 3 couleur car seul 2 valeur vrai et faux sont disponible.
ensuite si on veut que sat soit un problème on doit bien définir le ou le et et le non. (hésite pas à me dire si je me trompes mais je les définis surtout en fonction de mon intution logique)
donc pour moi le et veut juste dire rajouter une variable à un problème pour agrandir celui ci il n'a pas forcément fonction d'addition mais ajoute juste des données au problème . le non traduit juste un contraire d'une variable , si celle ci est comme ici binaire (2 choix) la valeur associée à une négation prends automatiquement l'unique autre variable disponible un ''non vrai '' implique un faux. ensuite le ou ici c'est plus compliqué je ne suis pas sûr de moi mais le ou traduit 2 possibilité or le ou doit être placé entre 2 variable à valeur différentes si on veut que le problème sat n'ai que 2 solution avec a vrai; b faux et c vrai ou totalement l'opposé a faux ; b vrai c faux. Or si le ou peut être placé entre 2 variables différentes prenant des valeur identiques le problème n'as plus de sens et a beaucoup plus de solutions. donc ma question portait sur le ou. Peut-il être placé entre 2 variable ( A B OU C) qui peuvent prendre la même valeur (vrai ou faux)? car si c'est le cas dans sa définition normale le problème n'a pas 2 solutions bien restreinte. voilà j'espère avoir été clair.
Le symbole "+" est un opérateur que tu connais bien. Il combine deux variables qu'on écrit de part et d'autre, par exemple "a+b". Pour fixer les idées on a qu'a dire qu'on parle des entiers. "+" est donc un opérateur qui prend 2 entiers et les combine pour faire un entier. par exemple 2+3 = 5. Jusque la tu me suis :) Bon maintenant parlons de "ou", "et" : ce sont également des opérateurs, seulement a la place de prendre des entiers en paramètres eux il prennent des booléens, c'est à dire des variables qui peuvent prendre comme valeur "vrai" ou "faux" et leur job et de combiner ses variables pour faire un nouveau booléen. (Exactement comme le + le faisait avec des entiers). "x et y" ça vaut "vrai" si et seulement si les deux variables valent vrai. "x ou y" ça vaut vrai si et seulement si au moins une des variables vaut vrai. De la même manière qu'on avait 2+3 =5 avec l’opérateur + dans les entiers on a donc par exemple: vrai et faux = faux, vrai ou faux = vrai, vrai et vrai = vrai, vrai ou vrai = vrai. faux ou faux = faux. avec les opérateurs "et" et "ou" dans les booléens. Donc ça devrait corriger/répondre à une partie de ta question. surtout ce que tu dis vers la fin sur "peut on placer le ou ....." ba on peut placer le "+" entre n'importe quels entiers. on peut placer le "ou" entre n'importe quels booléens. Le "non" c'est un opérateur qui ne prend qu'un booléen et le transforme en son contraire.
Donc le problème SAT c'est en fait une équation ici c'est l’équation "(a ou b) et (c ou (non a)) = vrai". Il s'agit de trouver si elle a au moins une solution. (elle pourrait ne pas avoir de solution. par exemple "a et b et (non a) = vrai" n'a pas de solutions, elle pourrait en avoir plusieurs aussi on s'en fout on se demande si il y en a au moins une). Donc je reformule: le problème SAT consiste à se demander, étant donnée une formule logique (faisant intervenir des variables booléennes et les opérateurs et ou etc....), si on peut trouver des valeurs des variables qui rendent l'expression vrai (lorsqu'on la calcule avec les règles que j'ai donnée). C'est plus clair sur le calcul logique et le problème SAT?
Pour ce qui est de le transformer en un problème de 3 couleurs ce n'est pas du tout facile à faire ni évident. maintenant que tu comprend mieux la question, je te suggères de te repasser lentement les étapes pour le faire (a partir de 6:30) dans la vidéo et de me dire ou tu bloques.
merci beaucoup en fait tu aurais peut être du dire tout cela dans ta vidéo mais c'est très clair maintenant merci beaucoup de prendre ton temps pour répondre à un abonné curieux et un peu perdu ;D
ptdrrrrrrrrr j'ai beau essayer, à chaque vidéo j'ai bien l'impression que malgré avoir bien écouté je comprends vraiment rien, enfin j'ai l'impression d'avoir compris alors que absolument pas..
Hésite pas à poser des questions à partir du premier passage qui te pose problème!
Je penses que je n'ai simplement pas de connaissances assez poussés pour comprendre le fond de ce que tu dis, même si il est vrai que c'est très très intéressant, je penses que je ne vais pas tarder à totalement comprendre tes propos à force de te regarder !
tu ne dis pas aussi si même on arrive un jour à résoudre rapidement un problème np complet le temps pour transformer un problème en un autre n'en fera pas patir au final sa résolution.
Il s'agit principalement qu'une question de mathématique théorique dans laquelle ce qui nous intéresse c'est la "complexité" de l'algorithme de résolution. C'est à dire la manière dont le temps de résolution progresse avec la taille du problème. Dans le cadre théorique ici, transformer un problème en un autre, n'est autorisé et n'a de sens que lorsque la transformation prend un temps polynomiale car ce qui nous interesse c'est de distinguer les complexites polynomiales (qu'on regroupe dans la meme famille) des autres. Du coup dans notre cadre theorique, transformer le probleme ne fait en patir sa resolution dans le sens ou si on se trouve dans la famille "polynomiale" avec une transformation polynomiale on reste dans cette famille. Dans un cadre pratique cependant transformer un algorithme polynomiale en un autre algorithme polynomial ce n'est en effet pas du tout anodin! et transformer le probleme peut etre infaisable en pratique. La question théorique est importante en fait a la limite, il existera toujours une taille de probleme à partir de laquelle la transformation polynomiale d'un probleme NP en un autre sera negligeable par rapport au temps pour le resoudre. Mais il est tout a fait possible de n'avoir aucune applications pratiques :)
ok merci ;)
Dommage que la vidéo ne s'adresse qu'au personnes ayant des bases suffisantes . Peut être que j comprendrai mieux après avoir appris toutes les terminologies utilisée ici.
Hello, je t'invite à prendre la vidéo dans l'ordre et à me poser une question au premier moment qui nécessite des explications additionnelles, ainsi que sur la terminologie qui te pose problème. :) ne pas hésiter.
Aie dommage que j'ai quitter l'école si tôt je pense que j'aurait eu un bon potentiel :/
je pense que le raisonnement logique finira par battre ou surpasser le raisonnement mathématique sur tous les niveau (un jour), vous me direz que la logique est fait partie des mathématiques, je vous dirai que c'est exactement ca le pbm...
Qu'entendez vous par raisonnement logique?
@@PasseScience : raisonnement direct, cas par cas/contraposée/absurde/contre-exemple/ récurrence...
@@gnosetech5381 Donc pour vous le raisonnement est un cadre formel, et vous ne voulez pas appelez cela des mathématiques? je ne suis pas sur de saisir la nuance que vous voulez introduire ou la these que vous voulez amener avec cette opposition math/raisonnement.
Je viens de casser 3-SAT. P=NP
Une nouvelle approche Des maths devient inevitable ,Elle ouvrira une nouvelle ere .Mais la DOXA fait toujours obstacle.jusqu a quand ???
J'ai rien compris... J'espère ne pas être le seul dans ce cas.
Il vous manque peut etre un peu d'acquis de connaissance pour ce sujet... Je vous conseille soit de revoir la video, soit de chercher un peu plus sur le net!
Ouais tu devrais reprendre la vidéo et chercher les termes que tu ne comprends pas un par un si tu veux comprendre, Passe-Science est une chaîne se voulant à mi-chemin entre la vulgarisation et l'approfondissement de culture sur des concepts touchant aux maths et à la physique, c'est pas totalement de la vulgarisation, perso j'adore ce concept !
@44DexterMorga: N’hésite pas a poser une question précise, si tu reprends la vidéo, arrête toi au premier passage qui te pose problème et demande, je me ferais une joie de te répondre.
le problème c'est que pour formuler une question il faudra deja avoir quelque notion sur le sujet, sinon ma première question sera "mais de quoi tu parle ?!!!" loll
alors je me demande plutot si vous pouvais me conseiller une documentation ou d'autres video qui servirons d'introduction pour les nuls , histoire de simplifier.
bien que j'ai ete perdu sur ce sujet, je trouve vous vidéos génial, et merci pour ce que vous faite. :)
Ba en gros, il existe un problème mathématique très célèbre qui s'appelle P=NP. Je n'attend pas forcement à ce que les gens le connaissent c'est pour ça que je tente d'expliquer justement de quoi ça parle :)
C'est pour ça qu'il me faut savoir ou tu plantes, par exemple si tu te
concentre sur le passage diagramme 1:20 à 2:10, est ce qu'un truc te pose problème, si oui à partir d'ou?