Gibt es NP-Probleme, nicht in P und nicht in NP Complete?

34

Gibt es bekannte Probleme in (und nicht in P ), die nicht N P sind ?NPPNP Complete sind? Meines Erachtens gibt es derzeit keine bekannten Probleme, bei denen dies der Fall ist, aber es wurde nicht ausgeschlossen, dass dies möglich ist.

Wenn es ein Problem gibt, das (und nicht P ), aber nicht N P - c o m p l e t e ist , wäre dies ein Ergebnis eines nicht vorhandenen Isomorphismus zwischen Instanzen dieses Problems und dem N P - c o m p l e t e set? Wenn dies der Fall ist, woher wissen wir, dass das N P -Problem nicht schwerer ist als das, was wir derzeit als N P - c o m p l e t identifizierenNPPNP-completeNP-completeNP gesetzt?NP-complete

vpiTriumph
quelle
1
Siehe auch diese verwandte Frage .
Raphael

Antworten:

25

Gibt es bekannte Probleme in NP (und nicht in P), die nicht NP Complete sind? Meines Erachtens gibt es derzeit keine bekannten Probleme, bei denen dies der Fall ist, aber es wurde nicht ausgeschlossen, dass dies möglich ist.

Nein, das unbekannt ist (mit Ausnahme der trivialen Sprachen und Σ * , diese beide wegen der Definition von many-one Reduzierungen nicht vollständig sind, in der Regel dieser beide werden ignoriert , wenn viel eine Verringerung Berücksichtigung). Das Vorhandensein eines N P -Problems, das für N P nicht vollständig ist, würde bedeuten, dass PN P nicht bekannt ist (obwohl allgemein angenommen). Wenn die beiden Klassen unterschiedlich sind, dann wissen wir, dass es Probleme in N P gibt, die nicht vollständig sind. Nehmen Sie ein Problem in P an .ΣNPNPPNPNPP

Wenn es ein Problem gibt, das NP (und nicht P), aber nicht NP Complete ist, ist dies das Ergebnis eines fehlenden Isomorphismus zwischen Instanzen dieses Problems und dem NP Complete-Satz?

Wenn die beiden Komplexitätsklassen unterschiedlich sind, gibt es nach dem Ladner-Theorem Probleme, die -Zwischenprodukte sind, dh sie liegen zwischen P und N P - c o m p l e t e .NPPNP-complete

Wenn dies der Fall ist, woher wissen wir dann, dass das NP-Problem nicht "schwerer" ist als das, was wir derzeit als NP-Komplettset bezeichnen?

Sie sind immer noch Polynomzeit reduzierbar auf Probleme , so dass sie nicht härter als seine N P - c o m p l e t e Probleme.NP-completeNP-complete

Kaveh
quelle
Es ist ein paar Jahre her, aber ich hatte den Eindruck, dass NP-Hard-Probleme in die Beschreibung des OP passen. Wo passen sie hinein?
Kevin
2
@ Kevin: Nein, NP-schwer bedeutet, dass ein Problem mindestens so schwer ist wie die schwersten Probleme in NP.
Huck Bennett
Was ist mit Problemen mit pseudopolynomieller Laufzeit?
Joe
@ Joe, ich bin mir nicht sicher, was du meinst, wenn du eine Frage hast, poste sie als neue Frage.
Kaveh
1
Natürlich unter der Annahme von P! = NP. Ein solches Problem wäre der Graph-Isomorphismus, oder?
Levi
11

Wie @Kaveh feststellte, ist diese Frage nur interessant, wenn wir annehmen ; Der Rest meiner Antwort geht davon aus, dass dies der Fall ist, und enthält meist Links, um Ihren Appetit weiter zu befeuchten. Unter dieser Annahme wissen wir nach Ladners Theorem, dass es Probleme gibt, die weder in P noch in N P C sind ; Diese Probleme werden N P -Zwischenprodukt oder N P I genannt . Interessanterweise kann Ladners Theorem auf viele andere Komplexitätsklassen verallgemeinert werden , um ähnliche Zwischenprobleme zu erzeugen. Ferner impliziert der Satz auch, dass es eine unendliche Hierarchie gibtPNPPNPCNPNPIvon Zwischenproblemen, die in nicht mehrmals miteinander reduzierbar sind .NPI

Leider ist es selbst mit der Annahme sehr schwierig, natürliche Probleme zu finden, die nachweislich N P I wären (natürlich haben Sie die künstlichen Probleme, die sich aus dem Beweis des Ladner-Theorems ergeben). Selbst wenn wir zu diesem Zeitpunkt P N P annehmen, können wir nur glauben, dass einige Probleme N P I sind, aber wir können es nicht beweisen. Wir kommen zu solchen Glauben , wenn wir vernünftige Beweise zu glauben , dass ein N P Problem nicht in ist N P C und / oder nicht in PPNPNPIPNPNPINPNPCP; oder gerade, wenn es für eine lange Zeit studiert wurde und vermieden wurde, in eine der Klassen zu passen. Diese Antwort enthält eine ziemlich umfassende Liste solcher Probleme . Es enthält Favoriten aller Zeiten wie Factoring, diskretes Log und Graph-Isomorphismus.

Interessanterweise haben einige dieser Probleme (bemerkenswert: Factoring und diskretes Log) polynomielle Zeitlösungen auf Quantencomputern (dh sie sind in ). Einige andere Probleme (wie der Graph-Isomorphismus) sind in B Q P nicht bekannt , und es gibt laufende Forschungen, um die Frage zu lösen. Andererseits wird vermutet, dass N P C B Q P , so dass die Leute nicht glauben, dass wir einen effizienten Quantenalgorithmus für SAT haben werden (obwohl wir eine quadratische Beschleunigung erzielen können); Es ist eine interessante Frage, sich Gedanken darüber zu machen, welche Art von Struktur N P ich brauche, um in B zu seinBQPBQPNPCBQPNPIBQP .

Artem Kaznatcheev
quelle
Ein wirklich aktuelles Ergebnis von Babai (siehe jeremykun.com/2015/11/12/… ) liefert einen quasipolynomialen Algorithmus für die Isomorphie von Graphen, der im Grunde genommen aus dem NPI entfernt wird, wenn das Ergebnis zutrifft. Interessanterweise war es das Problem, von dem nicht bekannt war, dass es
Uhr
1
@ FrédéricGrosshans mit einem quasipolynomialen Zeitalgorithmus entfernt Sie nicht aus dem NPI (in der Tat würde er Sie nicht einmal aus dem NPC entfernen, wenn Sie nicht strengere Annahmen treffen als nur P! = NP). Babais Ergebnis (wenn es richtig ist, was es wahrscheinlich ist) liefert nur Indizien dafür, dass GraphIso in P enthalten sein könnte, da in der Vergangenheit, als Quasipolynomalgorithmen für schwierige Probleme gefunden wurden, diese schließlich zu Polynomalgorithmen führten.
Artem Kaznatcheev
1
@ FrédéricGrosshans Babai hat die Behauptung der quasipolynomialen Laufzeit zurückgenommen . Anscheinend gab es einen Fehler in der Analyse.
Raphael
@Raphael Gemäß meiner vorherigen Bemerkung denke ich nicht, dass Babai, der das Quasipolynom zu Subexponential lockert, für die vorliegende Diskussion nicht besonders relevant ist.
Artem Kaznatcheev
Da dieser Kommentar immer noch hier ist, wollte ich nicht, dass er unkorrigiert bleibt. (Grundsätzlich habe ich alle Vorkommen von "Babai" auf der Website aufgespürt und denselben Kommentar gepostet.) Sie können alle Kommentare als veraltet markieren.
Raphael
7

Es sind keine NP- vollständigen Probleme in P bekannt . Wenn es einen Polynomzeitalgorithmus für ein NP- vollständiges Problem gibt, dann ist P = NP , da jedes Problem in NP eine Reduzierung der Polynomzeit auf jedes NP- vollständige Problem hat. (So ​​wird eigentlich " NP- vollständig" definiert.) Und wenn jedes NP- vollständige Problem außerhalb von P liegt , bedeutet dies natürlich, dass PNP ist . Wir sind uns nicht sicher, warum es schwierig ist, es auf die eine oder andere Weise zu zeigen. Wenn wir die Antwort auf diese Frage wüssten, würden wir wahrscheinlich viel mehr über P wissen undNP. Wir haben einige Beweistechniken, von denen wir wissen, dass sie nicht funktionieren (zum Beispiel Relativierung und natürliche Beweise), aber wir haben keine prinzipielle Erklärung, warum dieses Problem schwierig ist.

Wenn es in NP Probleme gibt, die nicht in P sind , dann gibt es tatsächlich eine unendliche Hierarchie von Problemen in NP zwischen denen in P und denen, die NP vollständig sind: Dies ist ein Ergebnis, das Ladner-Theorem genannt wird .

Hoffe das hilft!

templatetypedef
quelle
Bitte erklären Sie: Es ist nicht bekannt, dass NP-Probleme nicht in P sind. Sind nicht alle P schon in NP?
1
@ Shimano- Dies sind zwei verschiedene Konzepte: Alle Probleme in P sind bekanntermaßen in NP. Wir wissen jedoch nicht, ob es in NP keine Probleme gibt. Das heißt, wir wissen, dass P eine Teilmenge von NP ist, aber wir wissen nicht, ob NP eine Teilmenge von P ist. Klärt das die Dinge?
Templatetypedef
Die Dinge werden jetzt klarer. Vielen Dank für Ihre schnellen Antworten. Eine weitere Klarstellung ist erforderlich. Sie sagten: "Der Grund dafür ist, dass jedes Problem in NP eine Reduzierung der Polynomzeit auf jedes NP-vollständige Problem hat." Dies beweist, dass alle Probleme in NP automatisch NP-vollständig sind. Ich bin wieder ein bisschen verwirrt
@ Shimano- Nicht ganz. Die Richtung der Reduktion ist wichtig. Ein Problem ist NP-vollständig, wenn sich alle Probleme in NP auf dieses Problem reduzieren. Sie können auch zeigen, dass ein Problem NP-schwer ist, indem Sie ein bekanntes NP-vollständiges Problem auf dieses Problem reduzieren. Das Zeigen, dass ein Problem in NP auf ein bekanntes NP-vollständiges Problem reduziert wird, zeigt jedoch nichts Neues, da per Definition alle NP-Probleme auf alle NP-vollständigen Probleme reduziert werden.
Templatetypedef
1
@ Shimano-Ladner's Theorem besagt, dass, wenn P! = NP, es NP-Zwischenprobleme geben muss. Wenn es also keine NP-Zwischenprobleme gibt, dann ist P = NP. Und ja - wenn wir ein Problem in NP finden, das nicht in P ist, unabhängig davon, ob es in BQP ist, dann ist P! = NP.
Templatetypedef
5

P

PP

P


1 Ähnliches Problem: Der Subgraph-Isomorphismus ist in starkem Sinne NP-vollständig.


quelle
3 Jahre später scheint der Graph-Isomorphismus sehr nahe an P zu liegen (ein quasipolynialer Zeitalgorithmus wurde von Babai vorgeschlagen). Jeremykun.com/2015/11/12/…
Frédéric Grosshans
Babai widerrief die Behauptung der quasipolynomialen Laufzeit . Anscheinend gab es einen Fehler in der Analyse.
Raphael
Der Fehler in Babais Beweis wurde einige Tage später behoben.
David Bevan