Verallgemeinerter Satz von Ladner

45

Ladners Theorem besagt, dass wenn P ≠ NP ist, es eine unendliche Hierarchie von Komplexitätsklassen gibt, die ausschließlich P enthalten und ausschließlich in NP enthalten sind. Der Beweis verwendet die Vollständigkeit von SAT unter einer um ein Vielfaches verringerten NP. Die Hierarchie enthält Komplexitätsklassen, die durch eine Art Diagonalisierung aufgebaut sind und jeweils eine Sprache enthalten, auf die die Sprachen in den unteren Klassen nicht um ein Vielfaches reduzierbar sind.

Das motiviert meine Frage:

Sei C eine Komplexitätsklasse und sei D eine Komplexitätsklasse, die streng C enthält. Wenn D Sprachen enthält, die für einen bestimmten Begriff der Reduktion vollständig sind, gibt es eine unendliche Hierarchie von Komplexitätsklassen zwischen C und D in Bezug auf die Ermäßigung?

Genauer gesagt würde ich gerne wissen, ob Ergebnisse für D = P und C = LOGCFL oder C = NC für einen geeigneten Begriff der Reduktion bekannt sind.


Ladners Arbeit enthält bereits Theorem 7 für weltraumgebundene Klassen C, wie Kaveh in einer Antwort hervorhob. In seiner stärksten Form heißt das: Wenn NL ≠ NP, dann gibt es eine unendliche Folge von Sprachen zwischen NL und NP, deren Härte streng zunimmt. Dies ist etwas allgemeiner als die übliche Version (Satz 1), die von P ≠ NP abhängig ist. In Ladners Arbeit wird jedoch nur D = NP berücksichtigt.

András Salamon
quelle
1
Man kann zuerst die Frage stellen, die sich auf Klassen konzentriert, von denen wir bereits wissen, dass sie unterschiedlich sind. Gibt es zum Beispiel eine unendliche Hierarchie zwischen AC 0 und AC 0 [6] in Bezug auf Projektionen? Das sieht nach einer schwierigen Frage aus! :-)00
Michaël Cadilhac
Siehe auch cstheory.stackexchange.com/questions/52/… für eine Frage zum Intervall von P nach NP.
András Salamon

Antworten:

33

Die Antwort auf Ihre Frage lautet "Ja" für eine Vielzahl von Klassen und Reduktionen, einschließlich Logspace-Reduktionen und der von Ihnen erwähnten Klassen, wie in diesen Abhandlungen belegt:

H. Vollmer. Die Technik der Lückensprache wurde überarbeitet . Computer Science Logic, Vorlesungsskript in Computer Science Vol. 533, Seiten 389-399, 1990.

K. Regan und H. Vollmer. Lückensprachen und Log-Zeit-Komplexitätsklassen . Theoretical Computer Science, 188 (1-2): 101 & ndash; 116, 1997.

(Sie können gezippte Postscript-Dateien dieser Artikel hier herunterladen .)

Die Beweise folgen dem Grundprinzip von Uwe Schönings Erweiterung des Ladner-Theorems:

Uwe Schöning. Ein einheitlicher Ansatz, um Diagonalsätze in Komplexitätsklassen zu erhalten . Theoretical Computer Science 18 (1): 95-103, 1982.

Schönings Beweis war schon immer mein Lieblingsbeweis für Ladners Satz - er ist sowohl einfach als auch allgemein.

John Watrous
quelle
und was ist mit Versprechen Klassen?
Marcos Villagra
12

Es ist sehr wahrscheinlich, dass Sie dies in einer allgemeinen Umgebung erreichen können. Mit ziemlicher Sicherheit ein solches Ergebnis hat bereits in einer allgemeinen Einstellung bewiesen worden, aber die Referenzen entgeht mir im Moment. Also hier ist ein Argument von Grund auf neu.

Der Bericht unter http://oldblog.computationalcomplexity.org/media/ladner.pdf enthält zwei Beweise für Ladners Satz. Der zweite Beweis von Russell Impagliazzo erzeugt eine Sprache der Form { x 01 f ( | x | ) }, wobei x eine erfüllbare Formel codiert und f eine bestimmte polynomielle Zeitberechnungsfunktion ist. Das heißt, durch einfaches Auffüllen SAT mit der entsprechenden Anzahl von 1 s, können Sie ‚NP-Zwischen‘ Sets erhalten. Das Auffüllen wird durchgeführt, um über alle möglichen Polynomzeitverkürzungen "zu diagonalisieren", so dass keine Polynomzeitverkürzung von SAT auf L 1 erfolgtL1X01f(|X|)Xf1L1arbeiten (unter der Annahme ). Um zu beweisen, dass es unendlich viele Härtegrade gibt, sollte man im obigen Argument L 1 anstelle von SAT einsetzen und das Argument für L 2 = { x 0 1 f ( | x | ) | wiederholen können x L 1 }. Wiederholen Sie mit L i = { x 0 1 f ( | x | ) | x L i -PNPL1L2=X01f(|X|)|XL1Lich= }.X01f(|X|)|XLich-1

Es scheint klar, dass ein solcher Beweis auf die Klassen und D verallgemeinert werden kann , in denen (1) C ordnungsgemäß in D enthalten ist , (2) D eine vollständige Sprache unter C- Reduktionen hat, (3) die Liste aller C- Reduktionen kann rekursiv aufgezählt werden, und (4) die Funktion f ist in C berechenbar . Vielleicht ist die letzte Anforderung die einzige, die Anlass zur Sorge gibt, aber wenn Sie sich die Definition von f im Link ansehen , sieht es für die meisten vernünftigen Klassen C , die mir einfallen , sehr einfach zu berechnen aus.CDCDDCCfCfC

Ryan Williams
quelle
8

Ich denke , die Antwort ist positiv für und die einheitliche Version von N C . Ladners Beweis verwendet nicht viel anderes als das, was Sie angegeben haben, und die Tatsache, dass die kleinere Klasse rekursiv dargestellt wird und mit geringfügigen Modifikationen arbeiten sollte, aber ich habe die Details nicht überprüft. Schauen Sie sich Lances Beschreibung hier an .C=LNC


Aktualisieren

Lesen Sie Ladners Artikel über die Struktur der Polynomzeitreduzierbarkeit

Hier ist die Zusammenfassung: Zwei Begriffe der Polynomzeitreduzierbarkeit, die hier mit und P m bezeichnet werden , wurden von Cook bzw. Karp definiert. Die abstrakte Eigenschaft dieser beiden Beziehungen auf dem Gebiet der berechenbaren Mengen wird untersucht. Beide Beziehungen erweisen sich als dicht und haben minimale Paare. Ferner gibt es eine streng aufsteigende Sequenz mit einem minimalen Paar oberer Schranken zur Sequenz. Unsere Methode zur Darstellung der Dichte liefert das Ergebnis, dass es, wenn P N P ist, Mitglieder von N P - P gibt , die nicht polynomisch vollständig sind.TPmPPNPNP-P

THEOREM 1. Wenn B berechenbar ist und nicht in , dann existiert ein berechenbaren A , so dass A P , A P m B und B P T A .PEINEINPEINmPBBTPEIN

Siehe auch Abschnitt 6, in dem Verallgemeinerungen behandelt werden:

Satz 5 : Ist a Zeitklasse dann C m und C T sind reflexive und transitive Beziehungen und Theoreme 1-4 Halt mit P ersetzt durch C .CmCTCPC

THEOREM 7. Wenn ist ein Raum der Klasse dann C m und C T sind reflexive und transitive Beziehungen und Theoreme 1-4 Halt mit P ersetzt durch C .CmCTCPC

Die Begriffe Zeitklasse und Raumklasse sind in der Arbeit definiert.

Kaveh
quelle
So wie ich die Ladner- und Impagliazzo-Beweise verstand, schienen sie einige Zutaten zu verwenden, die spezifisch für NP, SAT und die Reduktion der Polynomzeit um ein Vielfaches waren. Meine Frage soll genau sein, ob diese Zutaten allgemeiner verwendet werden können.
András Salamon
@ András Salamon: Nein, tatsächlich verwendet Ladners Originalbeweis keine Tatsache über SAT, außer dass sie berechenbar ist (siehe Satz 1 oben). In Abschnitt 6 erörtert er die Eigenschaften, die erforderlich sind, damit eine Reduktion für seine Theoreme funktioniert. Ich denke ist eine Raumklasse. L
Kaveh
Ich denke, dass Theorem auch auf gleichförmige Schaltungsklassen verallgemeinert werden kann, so dass Theorem 1 auch für funktionieren würde (habe die Details nicht überprüft, ich werde es dem Beitrag hinzufügen, wenn ich es tue oder eine Referenz finde), aber ich tue es nicht Ich glaube nicht, dass es auf ungleichmäßige Versionen verallgemeinert werden kann, da der Beweis die Tatsache verwendet, dass die Komplexitätsklasse rekursiv dargestellt wird. Es wäre interessant zu wissen, ob Satz 1 auch für C = A C 0 (einheitliche Version) gilt, was Michaël Cadilhacs Kommentar unter dem Post beantworten würde. C=NCC=EINC0
Kaveh
5

Ich habe Peter Shor von Mathoverflow hier eine ähnliche Frage gestellt . Ihm zufolge ist er sich eines solchen Ergebnisses nicht bewusst.

NPP

EINichpBich-1pB

Ein weiteres interessantes Problem besteht darin, eine Verallgemeinerung von Ladner auf die Versprechungsversionen von semantischen Klassen wie promiseBPP, promiseMA usw. in Betracht zu ziehen.

Marcos Villagra
quelle
Ich habe vergessen zu erwähnen, dass dies natürlich nur in Bezug auf PH ist, und es scheint ein plausiblerer Ansatz zu sein, als nur eine Komplexitätsklasse zu nehmen.
Marcos Villagra
5
Link: mathoverflow.net/questions/9221/…
Ryan Williams
3
CBPPMEINNC
ja, die Aufzählung von Maschinen aus semantischen Klassen ist nicht rekursiv. Aber die Versprechen-Versionen von Semantik-Klassen (promiseBPP, promiseMA, ...) sind tatsächlich intaktisch.
Marcos Villagra