Komplexitätsklassentrennungen ohne Hierarchiesätze

Hierarchietheoreme sind grundlegende Werkzeuge. Eine gute Anzahl von ihnen wurde in einer früheren Frage gesammelt (siehe Welche Hierarchien und / oder Hierarchiesätze kennen Sie? ). Einige Komplexitätsklassentrennungen ergeben sich direkt aus Hierarchiesätzen. Beispiele für solche gut bekannte Trennungen: , , , $L\neq PSPACE$ $P\neq EXP$ $NP\neq NEXP$ $PSPACE\neq EXPSPACE$ .

Es folgt jedoch nicht jede Trennung aus einem Hierarchiesatz. Ein sehr einfaches Beispiel ist . Auch wenn wir nicht wissen, ob einer von ihnen den anderen enthält, sind sie immer noch unterschiedlich, da in Bezug auf Polynomtransformationen geschlossen ist, während nicht ist. $NP\neq E$ $NP$ $E$

Welches sind tiefere, bedingungslose, nicht relativierte Komplexitätsklassentrennungen für einheitliche Klassen, die sich nicht direkt aus einem Hierarchiesatz ergeben?

cc.complexity-theory complexity-classes hierarchy-theorems Andras Farago
quelle

Ich finde es etwas ungewöhnlich,

als Trennung zu bezeichnen. Auch ihre Ungleichheit ist trivial und sagt nichts Interessantes aus. AFAIK Alle interessanten Komplexitätsklassentrennungen für große Komplexitätsklassen beruhen irgendwann auf Hierarchiesätzen (und damit auf Diagonalisierung).

N P \neq E

$NP\neq E$

Kaveh

Es ist in der Tat ungewöhnlich,

als Trennung zu bezeichnen, da dies aus trivialen Gründen zutrifft. Ich habe es nur erwähnt, um ein einfaches Beispiel zu zeigen, in dem kein Hierarchiesatz benötigt wird.

N P \neq E

$NP\neq E$

Andras Farago

Äh, der Beweis von NP! = E hängt von einem Hierarchiesatz ab! Die Art und Weise, wie es funktioniert, ist, dass Sie zuerst NP = E annehmen und dann die Abschlusseigenschaften von NP verwenden, um daraus E = EXP abzuleiten, was gegen den Zeithierarchiesatz verstößt.

Scott Aaronson

Danke, Scott, du hast vollkommen recht.

war nicht das richtige Beispiel. Ich habe unter den Antworten eine bessere gepostet.

N P \neq E

$NP\neq E$

Andras Farago

Also auch solche Ungleichheiten setzen auf diagonalization:

aber

. Nett und doch nicht so trivial.

E \subseteq N P \subseteq A C^{0} \circ N P \subseteq A C^{0} \circ E \subseteq E X P

$E \subseteq NP \subseteq AC^0\circ NP \subseteq AC^0 \circ E \subseteq EXP$

E ⊊ E X P

$E \subsetneq EXP$

Kaveh

Antworten:

Ich würde gerne falsch dargestellt werden, aber ich glaube nicht, dass es derzeit einheitliche Untergrenzen gibt, die letztendlich nicht auf einem der Hierarchiesätze basieren. Unser derzeitiges Verständnis, wie wir die Gleichförmigkeit nutzen können, ist in diesem Sinne sehr begrenzt.

Andererseits gibt es viele einheitliche Untergrenzen, die sich nicht direkt aus Hierarchiesätzen ergeben, sondern einen Hierarchiesatz in Kombination mit anderen cleveren Tricks, Techniken und Ergebnissen verwenden, zum Beispiel:

[Hopcroft-Paul-Valiant]. Sie beweisen, dass (der nicht-diagonale Teil ihres Beweises), und verwenden dann die Tatsache, dass $\mathsf{CSL} \not\subseteq \mathsf{DTIME}(n)$ $\mathsf{DTIME}(n) \subseteq \mathsf{DSPACE}(n/\log n)$ $\mathsf{CSL} = \mathsf{NSPACE}(n)$ in Kombination mit der Raumhierarchie. Ihr Ergebnis + die implizieren auch . $\mathsf{DSPACE}(n) \nsubseteq \mathsf{DTIME}(n)$
Zeit-Raum-Kompromisse für die Zufriedenheit (siehe z. B. die Einführung von Buss-Williams und die darin enthaltenen Referenzen)
[Paul-Pippinger-Szemeredi-Trotter]. Verwendet eine nicht-triviale Simulation einer deterministischen Superlinearzeitmaschine durch eine schnellere Vier-Wechsel-Maschine in Kombination mit der deterministischen Zeithierarchie. $\mathsf{DTIME}(n) \neq \mathsf{NTIME}(n)$
Einheitliche Untergrenzen der bleibenden Karte [ Allender , Allender-Gore , Koiran-Perifel ]
[Williams] (obwohl es sich technisch gesehen um eine ungleichmäßige Untergrenze handelt, werden eine Reihe cleverer Ideen in Kombination mit der nichtdeterministischen Zeithierarchie verwendet) $\mathsf{NEXP} \not\subseteq \mathsf{ACC}^0$

Joshua Grochow
quelle

Ist die Trennung von Smolensky etwas, Sie gesucht haben? $\mathsf{AC}^0\subsetneq\mathsf{TC}^0$

Arne
quelle

Vielen Dank, dass ein gutes Ergebnis, aber ich bin auf der Suche nach Trennungen von

- Klassen, keine Schaltung Klassen.

u n i f o r m

$uniform$

Andras Farago

@AndresFarago: Uniform AC ^ 0 ist auch korrekt in Uniform TC ^ 0 enthalten.

Emil Jeřábek unterstützt Monica

@ EmilJeřábek: Gibt es einen Beweis dafür, dass Uniform

richtig in Uniform

, der die uneinheitliche Aussage nicht auch schon beweist? (Wenn nicht, dann scheint Ihr Beispiel unter das allgemeine Prinzip zu fallen, dass ungleichmäßige Untergrenzen stärker sind als gleichmäßige Untergrenzen, und ich denke, der OQ hat versucht, solche Antworten zu vermeiden ...)

{A C}^{0}

$\mathsf{AC}^0$

{T C}^{0}

$\mathsf{TC}^0$

Joshua Grochow,

Ich denke, die Ungleichmäßigkeit in den Beweisen ist sekundär zu der Tatsache, dass dies eher kleine Klassen sind, in denen wir ein gutes kombinatorisches / algebraisches Verständnis davon haben. Dh wir verstehen sie gut genug, um ein Objekt, das nicht in ihnen ist, direkt zu konstruieren. Wo es für größere Klassen kein solches Verständnis gibt, ist die einzige Methode, die wir kennen, die Diagonalisierung gegen die gesamte Klasse, um solche Objekte zu konstruieren.

Kaveh

$P_{P-comp}$

$P_{P-comp}$ $\mu$ $\mu$ $P\subseteq P_{P-comp}$ $P_{P-comp}=P$

$L\in P_{P-comp}$ $E$

E \subseteq P^{P_{P - c o m p}} (*)

$E\subseteq P^{P_{P-comp}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; (*)$

P_{P - c o m p} \neq P

$P_{P-comp}\neq P$

E \neq P

$E\neq P$

Referenz:

[1] R. Schuler, "Wahrheitstabellenschluss und Turing-Abschluss der durchschnittlichen Polynomzeit haben unterschiedliche Maße in EXP", CCC 1996, pdf

Andras Farago
quelle