Dialogue sur P vs NP (7)

Le dialogue avec Passe-Science, l'auteur de la vidéo P vs NP :

https://www.youtube.com/watch?v=8TrIW-4kfRg

Yu ：

Le problème P vs NP consiste à demander si NP = P? en réalité, c’est de demander si NP-complete = P? Dans ce cas, le problème P vs NP se concentre sur NP-complete.

Puisqu’on trouve qu’il est difficile de reconnaître NP-complete, on a déplacé le focus de NP-complete à NP :

Définition 1: NP est le problème décidable en temps polynomial sur une machine de Turing non-non-déterministe.

Définition 2: NP est un problème vérifiable en temps polynomial sur une machine de Turing.

NP est ainsi défini formellement. Au point de vue de la "forme", NP contient normalement P et NP-complete：

Mais au point de vue du "fond", ce n’est pas le cas. Puisque les attributs de NP comme « vérifiable et décidable » sont également partagés par P, de tels attributs ne pourraient pas être des attributs spécifiques de NP-complete, car NP-complete est quelque chose de nouveau, et ses attributs spécifiques n'ont pas encore été exprimés de manière formelle. En d'autres termes, ils ont disparu de NP. 

Par conséquent, NP-complete devient quelque chose comme une "boîte noire" dans NP, et la recherche de NP-complete dans NP devient une mission impossible. Tout comme si je cherche Toto dans un immeuble, et vous me dites que Toto est le voisin de Titi, mais je ne connais pas du tout Titi, il serait donc impossible de trouver Toto pour moi !

Dans ce sens, on pourrait questionner si la recherche de NP-complete dans NP (NP = P?) est comme si « les aveugles touchent un éléphant », . . .

Passe-Science ：

Je répond point par point:

"Le problème P vs NP consiste à demander si NP = P? en réalité, c’est de demander si NP-complete = P?"

Mathématiquement ça revient au même, P est différent de NP si et seulement si P est différent de NP-complet.

"car NP-complete est quelque chose de nouveau, et ses attributs spécifiques n'ont pas encore été exprimés de manière formelle"

Si ils le sont (exprimés formellement), les attributs spécifiques d'un problème NP-complet c'est précisément de pouvoir universellement exprimer n’importe quel autre problème pris dans NP. Pour être un problème NP-complet il faut qu'on puisse transformer en vous, en temps polynomial, un autre problème pris dans NP et n'importe lequel. C'est un attribut spécifique fort qui définit de manière formelle et précise l'ensemble dont on parle.

J'ajoute bien sur qu'à ce stade on ne pourra jamais fournir d'attributs qu'on puisse démontrer strictement spécifiques puisqu'on a pas

 résolu la conjecture, et que si la réalité est que P=NP alors P=NP=NP-complet et donc il n'y aura jamais aucun critère pour les départager, dans cet éventualité il n'existerait pas d'attributs spécifiques.

Mais pour le moment l'inverse est vrai aussi, l'attribut spécifique que je vous ai décrit ci dessus, vous ne pouvez pas non plus me démontrer qu'il n'est pas spécifique à NP-complet, si vous pouviez vous auriez résolu la conjecture.