Dort sind NP-Probleme, die nicht in P und nicht NP-Vollständig?

Question

Gibt es bekannte Probleme, die in $\mathsf{NP}$ (und nicht in $\mathsf{P}$, die nicht $\mathsf{NP}$ Vollständig?Mein Verständnis ist, dass es derzeit keine Probleme bekannt, wo dies der Fall ist, aber es wurde nicht ausgeschlossen, das ist eine Möglichkeit.

Wenn es ein problem ist, dass $\mathsf{NP}$ (und nicht $\mathsf{P}$), aber nicht $\mathsf{NP ext{-}complete}$, würde dies eine Folge der nicht vorhandenen Isomorphismus zwischen Instanzen des Problems und der $\mathsf{NP ext{-}complete}$ setzen?Wenn dies der Fall ist, wie würden wir wissen, dass $\mathsf{NP}$ problem ist nicht "schwieriger" als das, was wir derzeit erkennen, wie die $\mathsf{NP ext{-}complete}$ setzen?

Answer 1

Gibt es irgendwelche bekannten Probleme in NP (und nicht in P, die nicht NP-Vollständig?Mein Verständnis ist, dass es derzeit keine Probleme bekannt, wo dies der Fall ist, aber es wurde nicht ausgeschlossen, das ist eine Möglichkeit.

Nein, das ist nicht bekannt (mit der Ausnahme des trivialen Sprachen $\emptyset$ und $\Sigma^*$, diese zwei sind nicht vollständig, da von der definition vieler-one-Reduktionen werden in der Regel diese beiden ignoriert werden, wenn man viele-one-Reduktionen).Die Existenz von $\mathsf{NP}$ problem ist nicht komplett für $\mathsf{NP}$ w.r.t.viele-eine Polynom-Zeit-Reduktionen würde bedeuten, dass $\mathsf{P} eq\mathsf{NP}$, die nicht bekannt ist (obwohl allgemein angenommen).Wenn die beiden Klassen unterschiedlich sind, dann wissen wir, dass es Probleme in $\mathsf{NP}$, die nicht vollständig, nehmen jedes problem in $\mathsf{P}$.

Wenn es ist ein problem, das NP (und nicht P), aber nicht NP-Vollständige, wäre dies ein Ergebnis der nicht vorhandenen Isomorphismus zwischen Instanzen des Problems und der NP-Komplett-set?

Wenn die beiden Komplexität Klassen unterscheiden sich dann durch Ladner s theorem es gibt Probleme, die $\mathsf{NP}$-intermediate, d.h.Sie sind zwischen $\mathsf{P}$ und $\mathsf{NP ext{-}complete}$.

Wenn dies der Fall ist, wie würden wir wissen, dass die NP-problem ist nicht "schwieriger" als das, was wir derzeit erkennen, wie die NP-Komplett-set?

Sie sind noch in polynomieller Zeit reduzierbar auf $\mathsf{NP ext{-}complete}$ Problemen, so dass Sie kann nicht härter sein als $\mathsf{NP ext{-}complete}$ Problemen.

Answer 2

Wie @kaveh sagte, ist diese Frage nur interessant, wenn wir annehmen, dass $ p neq np $; Der Rest meiner Antwort nimmt dies als Annahme an und bietet hauptsächlich Links, um Ihren Appetit weiter zu nassen. Unter dieser Annahme wissen wir, dass es durch Ladners Theorem Probleme gibt, die weder bei $ P $ noch $ NPC $ sind. Diese Probleme werden als $ np $ -Intermediate oder $ npi $ bezeichnet. Interessanterweise kann Ladners Theorem auf verallgemeinert werden viele andere Komplexitätsklassen ähnliche Zwischenprobleme zu erzeugen. Ferner impliziert der Satz auch, dass es eine gibt Unendliche Hierarchie von Zwischenproblemen, die bei $ npi $ nicht mit Poly-Zeit zueinander reduzierbar sind.

Leider ist es auch bei der Annahme $ p neq np $ sehr schwierig, natürliche Probleme zu finden, die nachweislich $ NPI $ wären (natürlich haben Sie die künstlichen Probleme, die aus dem Beweis des Ladners Theorems kommen). Selbst wenn wir zu diesem Zeitpunkt $ p neq np $ annehmen, können wir nur einige Probleme glauben, $ npi $, aber nicht zu beweisen. Wir kommen zu solchen Überzeugungen, wenn wir vernünftige Beweise dafür haben, dass ein $ NP $ -Problem nicht in $ NPC $ und/oder nicht in $ p $ liegt. Oder gerade dann, wenn es lange Zeit studiert und vermieden wurde, sich in eine der beiden Klasse zu versetzen. Es gibt eine ziemlich umfassende Liste solcher Probleme in Diese Antwort. Es enthält solche Favoriten aller Zeiten wie Factoring, diskretes Protokoll und Graph-Isomorphismus.

Interessanterweise haben einige dieser Probleme (bemerkenswert: Factoring und diskretes Protokoll) Polynomzeitlösungen für Quantencomputer (dh sie sind in $ BQP $). Einige andere Probleme (z. B. Graph-Isomorphismus) sind nicht bekannt, dass sie in $ BQP $ sind, und es gibt laufende Untersuchungen zur Lösung der Frage. Andererseits wird vermutet, dass $ npc nicht subseteq bqp $, daher glauben die Leute nicht, dass wir einen effizienten Quantenalgorithmus für SAT haben werden (obwohl wir eine quadratische Geschwindigkeit erhöhen können); Es ist eine interessante Frage, über die man sich Sorgen machen muss Welche Art von Struktur $ NPI $ Probleme benötigen, um in $ BQP $ zu sein.

Answer 3

Keine NP-vollständige Probleme bekannt sind, werden in P.Wenn es ein Polynom-Zeit-Algorithmus für alle NP-vollständige problem ist, dann P = NP, denn jedes problem in NP hat ein Polynom-Zeit-Reduktion zu jedem NP-vollständige problem.(Das ist eigentlich wie "NP-complete" definiert ist.) Und natürlich, wenn jeder NP-vollständige problem liegt außerhalb des P, dies bedeutet, dass P ≠ NP.Wir sind nicht wirklich sicher, warum es schwer ist zu zeigen, dass es die eine oder andere Weise;wenn wir wussten, dass die Antwort auf diese Frage, würden wir wahrscheinlich eine ganze Menge mehr wissen über P und NP.Wir haben ein paar proof-Techniken, die wir kennen, nicht funktionieren (Relativierung und Natürliche Beweise, zum Beispiel), aber nicht über eine grundsätzliche Erklärung, warum dieses problem ist schwer.

Wenn es Probleme in der NP die nicht in P, dann gibt es eigentlich eine unendliche Hierarchie von Problemen in NP zwischen denjenigen, die sich in P und diejenigen, die NP abgeschlossen:dies ist ein Ergebnis genannt Ladner s theorem.

Hoffe, das hilft!

Answer 4

Es gibt einige Probleme, die NP sind, aber niemand weiß, dass sie NP-Complete oder $ P $ sind, wie Graph Isomorphismus¹. Aber da ich weiß, dass es für solche Probleme keine besondere Komplexitätsklasse gibt, kann ich mich jedoch irren.

Kann sein, es ist $ p $, z. B. vorher AKs Algorithmus Niemand weiß, dass Primalitätstests $ P $ oder NPC ist.

Es gibt auch einige Probleme, die NPC sind, aber nicht in starker Sinn oder Schwach NP-Complete, wie 2-Partition Das Problem bedeutet, wenn die Eingangszahlen in der Polynomreihenfolge der Eingabemaßgröße sind, können diese Probleme in $ p $ gelöst werden (oder es gibt einen Pseudo -Polynomzeitalgorithmus für sie).

---

¹ Ähnliches Problem: Subgrafik -Isomorphismus ist in starker Sinne NP-Vervollständigung.