Le dialogue avec Passe-Science, l'auteur de la vidéo P vs NP :
Yu Li : Je suis d’accord, « Si on a P différent de NP alors on aurait bien disjonction entre P et NP-Complet.
Le problème est que, les objets sont désignés et reconnus par des concepts, et le concept est formé par la définition dont la connotation consiste des attributs qui représentent l’essence des objets. Par conséquent, un objet désigné par un concept ainsi que sa reconnaissance dépend de la définition du concept.
Puisque les attributs comme « vérifiable » et « décidable » dans Définition 1 et Définition 2 sont partagés par les problèmes P, ils ne peuvent pas capturer l’essence du « vrai NP », autrement dit, « NP » désigné par Définition 1 ou Définition 2 peut-être n’est pas le « vrai NP », alors comment peut-on trouver NP different de P à travers ce « NP »?
C’est pour ça que je questionne sur la definition de « NP », …
Passe-Science : En fait je pense que surtout que la definition ne convient pas à ce que toi tu aimerais qu'elle désigne, mais c'est subjectif. Rien empêche de définir ce qu'est un chat, et de définir ensuite ce qu'est un animal, meme si on sait qu'être un chat impliquera être un animal. Je ne dirais pas qu'il y a un "problème" dans la definition d'animal, c'est juste une classe plus large. Et il est légitime ensuite de se demander s'il existe d'autres animaux que des chats, ou d'autres NP que des P.
La definition que tu aimerais être celle de NP me semble être celle de NP-complet, c'est juste qu'a mon avis tu veux faire coller ton "concept" dans la definition NP alors que ton concept semble plutôt être celui de NP-complétude. Mais il sera impossible de définir NP-complet d'une manière qui montrerait clairement qu'on a autre chose que P puisque ca serait répondre à la conjecture pour le moment irrésolue.
Si on démontre un jour P different de NP, alors a mon avis, la definition que tu cherches c'est juste NP-complet. C'est a dire les "rapidement vérifiables et non trivialement décidables" (dans ce cas la ou P different de NP)
Aucun commentaire:
Enregistrer un commentaire