Gibt es "NP-Intermediate-Complete" -Probleme?

12

Angenommen, P NP.≠

Ladners Theorem besagt, dass es NP-Zwischenprobleme gibt (Probleme in NP, die weder in P noch in NP-Complete vorliegen). Ich habe einige verschleierte Online-Referenzen gefunden, die darauf hindeuten (ich denke), dass es in NPI viele "Ebenen" gegenseitig reduzierbarer Sprachen gibt, die definitiv nicht alle in einer zusammenfallen.

Ich habe einige Fragen zur Struktur dieser Ebenen.

  1. Gibt es "NP-Intermediate-Complete" -Probleme, dh NP-Intermediate-Probleme, auf die jedes andere NP-Intermediate-Problem polyzeitreduzierbar ist?
  2. Sortieren Sie NP - P in Äquivalenzklassen, wobei die gegenseitige Reduzierbarkeit die Äquivalenzrelation ist. Ordnen Sie nun diese Äquivalenzklassen wie folgt an: wenn sich die Probleme in B auf Probleme in A reduzieren (die Äquivalenzklasse NP-Complete ist also eindeutig das maximale Element). Ist dies eine Gesamtordnung (dh die Probleme sind in einer unendlichen absteigenden Kette angeordnet)? Wenn nicht, hat die "Baumstruktur" der Teilordnung einen endlichen Verzweigungsfaktor?EIN>BBEIN
  3. Gibt es weitere interessante bekannte Strukturkomponenten von NP-P? Gibt es interessante offene Fragen zur zugrunde liegenden Struktur?

Wenn einer davon derzeit unbekannt ist, würde mich das ebenfalls interessieren.

Vielen Dank!

cc.complexity-theory np np-intermediate GMB
quelle
2
Eine schwache Version davon ist, dass es "Graph-Isomorphism-Complete" -Probleme gibt.
Suresh Venkat
6
Die Antwort auf 1. ist "Ja und Nein". Ich denke: Ja, denn wie Suresh sagt, kann es GI-vollständige Probleme geben (und vollständige Probleme für andere Probleme π ). Und nein, denn nach Ladners Beweis gibt es eine unendliche Hierarchie von N P -Zwischenklassen, und wenn ich mich nicht irre, würde ein N P -Zwischen-Vollständiges Problem diese Hierarchie kollabieren (und somit durch Widerspruch beweisen, dass P = N P ). Auf die gleiche Weise wie die Polynom-Hierarchie kann es kein vollständiges Problem geben, wenn sie nicht zusammenbricht. ππNPNPP=NP
Bruno
Danke, Bruno - sind diese Informationen alle in Ladners Originalarbeit zu finden, oder sollte es andere relevante Quellen geben?
GMB
Sie können auch einen Blick auf das Papier von Downey und Fortnow werfen: Uniformly Hard Languages ; in dem der Ladner-Theorem-Beweis in Anhang A.1 zeigt, dass die Polynomzeitgrade berechenbarer Sprachen eine dichte partielle Ordnung sind. Sie vermuten auch, dass es unvollständige, gleichmäßig harte Mengen gibt, wenn es in NP gleichmäßig harte Mengen gibt.
Marzio De Biasi
1
Eine weitere Referenz für 1. und eine möglicherweise nützliche Ressource finden Sie in Ryans Antwort und in Schönings darin zitiertem Artikel .
Sasho Nikolov

Antworten:

31

Ich habe nicht wirklich Referenzen für diese Ergebnisse - sie sind nicht schwer zu beweisen, wenn Sie Ladners Theorem verstehen.

  1. Nein, für jede NP-unvollständige Menge A gibt es eine andere Menge B, die genau zwischen A und SAT liegt.

  2. Diese Äquivalenzklassen werden als Polynom-Viel-Eins-Grade bezeichnet. Sie können jedes endliche Poset in die Grade unter NP einbetten. Insbesondere sind die Abschlüsse nicht vollständig geordnet oder endlich verzweigt.

  3. Das hängt alles davon ab, was Sie mit "interessant" meinen. Es gibt eine große Theorie der Gradstruktur der berechenbaren Mengen (siehe zum Beispiel Soares Buch ), und viele dieser Fragen wurden nicht auf Polynomzeitmengen übertragen. Können Sie zum Beispiel NP-Mengen A und B haben, deren Verknüpfung SAT entspricht und deren Erfüllung der leeren Menge entspricht?

Lance Fortnow
quelle
1
EINBC(x,y)∈Cx∈EINy∈B
8
Diese sind hinsichtlich der Gittertheorie : die Join einer Teilmenge ist die kleinste obere gebunden (falls vorhanden) und die treffen sich die untere Grenze.
Bruno