Y at-il des problèmes NP, pas dans P et non NP complète?

Question

Y a-t-il des problèmes connus dans $ \ mathsf {NP} $ (et non en $ \ mathsf {P} $) qui ne sont pas $ \ mathsf {NP} $ complète? Je crois comprendre qu'il n'y a pas de problèmes actuellement connus où cela est le cas, mais il n'a pas été exclu comme possibilité.

S'il y a un problème qui est $ \ mathsf {NP} $ (et non $ \ mathsf {P} $) mais pas $ \ mathsf {NP \ texte {-} complet} $, serait-ce en raison de pas entre les instances existantes isomorphisme de ce problème et le $ \ mathsf {NP texte de {- complet}} $ set? Si ce cas, comment pourrions-nous savoir que le $ \ mathsf {NP} $ problème n'est pas 'plus difficile' que ce que nous identifions actuellement comme $ \ mathsf {NP de texte {-} complet}? $ Set

Answer 1

  

Y a-t-il des problèmes connus dans NP (et non en P) qui ne sont pas NP complète? Je crois comprendre qu'il n'y a pas de problèmes actuellement connus où cela est le cas, mais il n'a pas été exclu comme possibilité.

Non, cela est inconnu (à l'exception des langues triviales $ \ emptyset $ et $ \ Sigma ^ * $, ces deux ne sont pas complètes en raison de la définition d'un grand nombre-une des réductions, généralement ces deux sont ignorés lors de l'examen réductions beaucoup un). Existence d'un $ \ mathsf {NP} $ problème qui n'est pas complet pour $ \ mathsf {NP} $ w.r.t. beaucoup-une réduction du temps polynomiale impliquerait que $ \ mathsf {P} \ neq \ mathsf {NP} $ qui est inconnu (bien que largement admis). Si les deux classes sont différentes, nous savons qu'il ya des problèmes dans $ \ mathsf {NP} $ qui ne sont pas complètes, prenez tout problème dans $ \ mathsf {P} $.

  

S'il y a un problème qui est NP (et non P) mais pas NP complète, serait-ce pas en raison de isomorphisme existant entre les instances de ce problème et le NP Set complet?

Si les deux classes de complexité sont différentes, par Ladner il y a des problèmes qui sont $ \ mathsf {NP } $ - intermédiaire, à savoir qu'ils sont entre $ \ mathsf {P} $ et $ \ mathsf {NP \ texte {-}. complet} $

  

Si ce cas, comment pourrions-nous savoir que le problème NP n'est pas « plus difficile » que ce que nous identifions actuellement le NP Set complet?

Ils sont toujours réductibles polynomiale à $ \ mathsf {NP texte de {-} complet} $ problèmes afin qu'ils ne peuvent pas être plus difficile que $ \ mathsf {NP \ texte {-} complets}. $ Problèmes

Answer 2

Comme @Kaveh dit, cette question est intéressante que si nous supposons $ P \ NEQ NP $; le reste de ma réponse prend cela comme une hypothèse, et fournit la plupart du temps des liens pour mouiller davantage votre appétit. Sous cette hypothèse, le théorème de Ladner, nous savons qu'il ya des problèmes qui ne sont ni en $ P $ et $ NPC $; ces problèmes sont appelés $ NP $ -intermédiaire ou $ NPI $. Il est intéressant, le théorème de Ladner peut être généralisé à beaucoup d'autres classes de complexité pour produire des problèmes similaires intermédiaires. En outre, le théorème implique aussi qu'il existe une hiérarchie infinie des problèmes intermédiaires qui ne sont pas réductibles poly-temps l'autre en $ NPI $.

Malheureusement, même avec l'hypothèse $ P \ NEQ NP $, il est très difficile de trouver des problèmes naturels qui seraient démontrable $ NPI $ (bien sûr, vous avez des problèmes artificiels provenant de la preuve du théorème de Ladner). Ainsi, même en supposant $ P \ NEQ NP $ à l'heure actuelle, nous ne pouvons croire que certains problèmes à $ NPI $, mais pas le prouver. Nous venons à ces croyances quand nous avons des preuves raisonnables de croire qu'un problème NP $ est pas $ PNJ $ et / ou non en $ P $; ou juste au moment où il a été étudié depuis longtemps et montage évité dans une ou l'autre classe. Il y a une liste assez exhaustive de ces problèmes dans cette réponse . Il comprend des favoris de tous les temps que l'affacturage, logarithme discret et graphique -isomorphisme.

Fait intéressant, certains de ces problèmes (notable: affacturage et log discret) ont des solutions de temps polynomiale sur les ordinateurs quantiques (à savoir qu'ils sont en $ BQP $). D'autres problèmes (tels que le graphique -isomorphisme) ne sont pas connus pour être en $ BQP $, et il y a des recherches en cours pour résoudre la question. D'autre part, on soupçonne que $ NPC \ not \ subseteq BQP $, donc les gens ne croient pas que nous aurons un algorithme quantique efficace pour SAT (bien que nous pouvons obtenir une vitesse du second degré vers le haut); il est une question intéressante à se soucier de ce type de structure $ NPI problèmes de $ ont besoin pour être en $ BQP $ .

Answer 3

Non NP problèmes COMPLETES sont connus pour être P . S'il y a un algorithme polynomial pour tout NP problème -complete, puis P = NP , car tout problème dans NP a une réduction du temps polynomiale à chaque -complete NP problème. (Qui est en fait comment " NP -complete" est défini.) Et évidemment, si tous les NP problème COMPLETES se situe en dehors de P , ce moyen que P ? NP . Nous ne sommes pas vraiment pourquoi il est difficile de le montrer d'une façon ou l'autre; si nous savions que la réponse à cette question, nous serions probablement savons beaucoup plus sur P et NP . Nous avons quelques techniques de preuve que nous savons ne fonctionnent pas (relativisation et preuves naturelles, par exemple), mais ne pas une explication fondée sur des principes pour expliquer pourquoi ce problème est difficile.

S'il y a des problèmes dans NP qui ne sont pas dans P , puis il y a effectivement une hiérarchie infinie de problèmes NP entre ceux P et ceux qui sont NP complète: ce résultat est appelé théorème de Ladner .

Hope this helps!

Answer 4

Il y a des problèmes qui sont NP, mais personne ne sait qu'ils sont NP-complet ou $ P $, comme graphique isomorphie ¹ . Mais comme je sais qu'il n'y a pas de classe de complexité particulière pour les problèmes d'un tel, peut-être que je me trompe, cependant.

est peut être son $ P $, avant par exemple AKS algorithme ne connaît le test de primalité est $ P $ ou NPC.

En outre il y a des problèmes qui sont PNJ mais pas dans forte sens ou weakly NP-complet , comme 2-Partition problème, des moyens, si les numéros d'entrée sont en ordre polynôme de taille d'entrée, ces problèmes peuvent être résolus en $ P $ (ou il y a un algorithme pseudo polynôme pour eux).

---

¹ Des problèmes similaires. est NP-complet dans le sens fort