Y a-t-il des problèmes NP, pas en P et pas NP Complete?

34

Existe-t-il des problèmes connus dans (et non dans ) qui ne sont pas terminés? Je crois comprendre qu'il n'y a actuellement aucun problème connu dans ce cas, mais cela n'a pas été exclu comme une possibilité. NPPNP

S'il y a un problème qui est (et non ) mais pas , est-ce le résultat de l'absence d'isomorphisme existant entre les instances de ce problème et l'ensemble ? Dans ce cas, comment saurions-nous que le problème n'est pas plus difficile que ce que nous identifions actuellement comme l'ensemble ?NPPNP-completeNP-completeNPNP-complete

vpiTriumph
la source
1
Voir aussi cette question connexe .
Raphael

Réponses:

25

Existe-t-il des problèmes connus dans NP (et non dans P) qui ne sont pas complets? Je crois comprendre qu'il n'y a actuellement aucun problème connu dans ce cas, mais cela n'a pas été exclu comme une possibilité.

Non, cela est inconnu (à l'exception des langages triviaux et , ces deux ne sont pas complets en raison de la définition de plusieurs réductions, généralement ces deux sont ignorés lors de l'examen de plusieurs réductions). L'existence d'un problème qui n'est pas complet pour rapport à plusieurs réductions de temps polynomiales impliquerait que qui n'est pas connu (bien que largement admis) . Si les deux classes sont différentes alors nous savons qu'il y a des problèmes dans qui ne sont pas complets pour cela, prenez n'importe quel problème dans .Σ N P N P PN P N P PΣNPNPPNPNPP

S'il y a un problème qui est NP (et non P) mais pas NP Complete, est-ce le résultat de l'absence d'isomorphisme existant entre les instances de ce problème et l'ensemble NP Complete?

Si les deux classes de complexité sont différentes, alors selon le théorème de Ladner, il y a des problèmes qui sont intermédiaires, c'est-à-dire qu'ils sont entre et .P N P - c o m p l e t eNPPNP-complete

Si ce cas, comment saurions-nous que le problème de NP n'est pas «plus difficile» que ce que nous identifions actuellement comme l'ensemble NP complet?

Ils sont toujours polynomiaux et réductibles aux problèmes , ils ne peuvent donc pas être plus difficiles que les problèmes .N P - c o m p l e t eNP-completeNP-complete

Kaveh
la source
Cela fait quelques années, mais j'avais l'impression que les problèmes NP-Hard correspondent à la description du PO, où se situent-ils?
Kevin
2
@Kevin: Non, NP-hard signifie qu'un problème est au moins aussi difficile que les problèmes les plus difficiles dans NP.
Huck Bennett
Qu'en est-il des problèmes avec le temps d'exécution pseudo-polynomial?
Joe
@Joe, je ne sais pas ce que tu veux dire, si tu as une question, poste-la comme une nouvelle question.
Kaveh
1
Oh, bien sûr en supposant que P! = NP. Un tel problème serait l'isomorphisme graphique, non?
levi
11

Comme l'a déclaré @Kaveh, cette question n'est intéressante que si nous supposons ; le reste de ma réponse prend cela comme une hypothèse, et fournit principalement des liens pour vous donner encore plus faim. Dans cette hypothèse, par le théorème de Ladner, nous savons qu'il y a des problèmes qui ne sont ni en ni en ; ces problèmes sont appelés intermédiaire ou . Chose intéressante, le théorème de Ladner peut être généralisé à de nombreuses autres classes de complexité pour produire des problèmes intermédiaires similaires. De plus, le théorème implique également qu'il existe une hiérarchie infinie de problèmes intermédiaires qui ne sont pas poly-temps réductibles les uns aux autres dans .P N P C N P N P I N P IPNPPNPCNPNPINPI

Malheureusement, même avec l'hypothèse il est très difficile de trouver des problèmes naturels qui seraient prouvablement (bien sûr, vous avez les problèmes artificiels provenant de la preuve du théorème de Ladner). Ainsi, même en supposant à ce moment, nous ne pouvons que croire que certains problèmes sont mais pas le prouver. Nous arrivons à de telles croyances lorsque nous avons des preuves raisonnables de croire qu'un problème n'est pas dans et / ou pas dans ; ou juste quand il a été étudié pendant longtemps et a évité de s'intégrer dans l'une ou l'autre classe. Il y a une liste assez complète de ces problèmes dans cette réponseN P I P N P N P I N P N P C PPNPNPIPNPNPINPNPCP. Il comprend des favoris de tous les temps tels que l'affacturage, le journal discret et l'isomorphisme graphique.

Fait intéressant, certains de ces problèmes (notables: factorisation et journal discret) ont des solutions temporelles polynomiales sur les ordinateurs quantiques (c'est-à-dire qu'ils sont en ). Certains autres problèmes (tels que l'isomorphisme des graphes) ne sont pas connus pour être dans , et des recherches sont en cours pour résoudre la question. D'un autre côté, on soupçonne que , donc les gens ne croient pas que nous aurons un algorithme quantique efficace pour SAT (bien que nous puissions obtenir une vitesse quadratique); c'est une question intéressante de s'inquiéter de quel type de problèmes de structure ont besoin pour être en .B Q P N P C BQPBQPNPCBQPNPIBQP

Artem Kaznatcheev
la source
Un résultat très récent de Babai (voir jeremykun.com/2015/11/12/… ) donne un algorithme quasipolynomial pour l'isomorphisme des graphes, le supprimant essentiellement du NPI, si le résultat est valable. Fait intéressant, c'était le problème qui n'était pas connu pour être dans BQP
Frédéric Grosshans
1
@ FrédéricGrosshans ayant un algorithme de temps quasi-polynomial ne vous supprime pas du NPI (en fait, il ne vous supprimera même pas du NPC à moins que vous ne fassiez des hypothèses plus fortes que P! = NP). Le résultat de Babai (s'il est correct, ce qu'il est probablement) ne fournit que des preuves circonstancielles que GraphIso pourrait être en P, car dans le passé, lorsque des algorithmes quasi-polynomiaux pour des problèmes difficiles ont été trouvés, ils ont finalement conduit à des algorithmes polynomiaux.
Artem Kaznatcheev
1
@ FrédéricGrosshans Babai a rétracté la revendication de durée d'exécution quasi-polynomiale . Apparemment, il y avait une erreur dans l'analyse.
Raphael
@Raphael d'après mon commentaire précédent, je ne pense pas que Babai assouplissant le quasipolynôme en subexponentiel ne soit pas particulièrement pertinent pour la discussion en cours.
Artem Kaznatcheev
Comme ce commentaire est toujours là, je ne voulais pas qu'il reste non corrigé. (Fondamentalement, j'ai retrouvé toutes les occurrences de "Babai" sur le site et publié le même commentaire.) N'hésitez pas à signaler tous les commentaires pour vous sentir obsolètes en tant que tels.
Raphael
7

Non NP Les problèmes sont connus pour être en P . S'il existe un algorithme à temps polynomial pour tout problème NP- complet, alors P = NP , car tout problème dans NP a une réduction du temps polynomial à chaque problème NP- complet. (C'est en fait ainsi que " NP- complet" est défini.) Et évidemment, si chaque problème NP- complet se situe en dehors de P , cela signifie que PNP . Nous ne savons pas vraiment pourquoi il est difficile de le montrer dans un sens ou dans l'autre; si nous connaissions la réponse à cette question, nous en saurions probablement beaucoup plus sur P etNP . Nous avons quelques techniques de preuve que nous savons ne pas fonctionner (relativisation et preuves naturelles, par exemple), mais nous n'avons pas d'explication de principe pour expliquer pourquoi ce problème est difficile.

S'il y a des problèmes dans NP qui ne sont pas dans P , alors il y a en fait une hiérarchie infinie de problèmes dans NP entre ceux dans P et ceux qui sont NP complets: c'est un résultat appelé théorème de Ladner .

J'espère que cela t'aides!

templatetypedef
la source
veuillez expliquer: Aucun problème dans NP n'est connu pour ne pas être dans P? Tous les P ne sont pas déjà dans NP?
1
@ Shimano- Ce sont deux concepts différents: Tous les problèmes de P sont connus pour être dans NP. Cependant, nous ne savons pas si des problèmes dans NP ne sont pas dans P. Autrement dit, nous savons que P est un sous-ensemble de NP, mais nous ne savons pas si NP est un sous-ensemble de P. Est-ce que cela clarifie les choses?
templatetypedef
Les choses deviennent plus claires maintenant. Merci beaucoup pour vos réponses rapides. Encore une clarification nécessaire. Vous avez dit: "La raison en est que tout problème dans NP a une réduction du temps polynomial pour chaque problème NP-complet." Cela prouve que tous les problèmes dans NP sont automatiquement NP-complets? Je suis encore un peu confus
@ Shimano- Pas tout à fait. Le sens de la réduction est important. Un problème est NP-complet si tous les problèmes de NP se réduisent à ce problème. Vous pouvez également montrer qu'un problème est NP-difficile en réduisant un problème NP-complet connu à ce problème. Cependant, montrer qu'un problème dans NP se réduit à un problème NP-complet connu ne montre rien de nouveau, car par définition tous les problèmes NP se réduisent à tous les problèmes NP-complets.
templatetypedef
1
@ Le théorème de Shimano-Ladner dit que si P! = NP, alors il doit y avoir des problèmes NP-intermédiaires, donc s'il n'y a pas de problèmes NP-intermédiaires, alors P = NP. Et oui - si nous pouvons trouver un problème dans NP qui n'est pas dans P, qu'il soit dans BQP, alors P! = NP.
templatetypedef
5

Il y a des problèmes qui sont NP, mais personne ne sait qu'ils sont NP-Complete ou , comme l' isomorphisme de graphe 1 . Mais comme je sais qu'il n'y a pas de classe de complexité spéciale pour de tels problèmes, je me trompe peut-être.P

Peut-être que c'est , par exemple avant l' algorithme AKS , personne ne sait que le test de primalité est ou NPC.PP

Il y a aussi certains problèmes qui sont NPC mais pas au sens fort ou faiblement NP-Complete , comme un problème à 2 partitions , signifie que si les nombres d'entrée sont dans l'ordre polynomial de la taille d'entrée, ces problèmes peuvent être résolus en (ou il y a un pseudo-algorithme temporel polynomial pour eux).P


1 Problème similaire: l'isomorphisme du sous-graphe est NP-complet au sens fort.


la source
3 ans plus tard, l'isomorphisme graphique semble être très proche de P (un algorithme de temps quasi-polynial a été proposé par Babai) jeremykun.com/2015/11/12/…
Frédéric Grosshans
Babai a rétracté la revendication de l'exécution quasi-polynomiale . Apparemment, il y avait une erreur dans l'analyse.
Raphael
L'erreur dans la preuve de Babai a été corrigée quelques jours plus tard.
David Bevan