Le dialogue avec Passe-Science, l'auteur de la vidéo P vs NP :
Yu Li : 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 ?
Passe-Science : 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.
Ne pas hésiter à préciser votre question si je n'y ai pas répondu.
Aucun commentaire:
Enregistrer un commentaire