Le dialogue avec Passe-Science, l'auteur de la vidéo P vs NP :
Yu Li : 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.
Passe-Science : 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.
Aucun commentaire:
Enregistrer un commentaire