Große Klassen, die LOGSPACE enthalten, für die strenge Einschlüsse nicht bekannt sind

Die Wikipedia-Seite auf PSPACE erwähnt, dass die Einbeziehung nicht als streng bekannt ist (leider ohne Verweise). $NL\subset PH$

F1: Was ist mit und - sind diese bekanntermaßen streng? $L\subset PH$ $L\subset P^{\#P}$

F2: Wenn nein, gibt es eine etablierte Klasse die und für die nicht bekannt ist, ob die Einbeziehung streng ist? $C$ $P^{\#P}$ $L\subset C$

Frage 3: Werden solche Einschlüsse in der Literatur diskutiert?

cc.complexity-theory complexity-classes logspace Łukasz Grabowski
quelle

Ich denke für Q2 meinst du streng in PSPACE enthalten?

Sasho Nikolov

AFAIK, die einzige bekannte Trennung für ist der . Ich glaube nicht, dass bekannt ist, ob eine der in der Frage genannten Klassen einen überlogarithmischen Raum simulieren kann, so dass auch nicht bekannt ist, dass sie streng sind. (Nicht zu wissen, eine Trennung ist kein Ergebnis, so dass wahrscheinlich der Grund gibt es keine Verweise.)

L

$\mathsf{L}$

Kaveh

Selbst für kleinere Klassen als , wie uniform , ist nicht bekannt, dass die Einschlüsse von Q1 streng sind. Ich denke, nach dem gegenwärtigen Kenntnisstand ist im Wesentlichen jede Klasse zwischen und eine positive Antwort auf Q2.

L

$\mathsf{L}$

{N C}^{1}

$\mathsf{NC}^1$

C

$C$

P^{# P}

$\mathsf{P}^{\mathsf{\# P}}$

P S P A C E

$\mathsf{PSPACE}$

Joshua Grochow

Ihr Fragentitel lautet "Größte Klasse". Meinst du nicht "kleinste Klasse"?

Shaull

Es ist nicht einmal bekannt, ob streng in PH enthalten ist. enthält TC ^ 0 streng durch ein Hierarchie-Argument, aber wie Joshua Grochow bereits erwähnte, ist dies für NC ^ 1 nicht bekannt. Für Q2 kannst du CH nehmen.

A C^{0} [6]

$AC^0[6]$

P^{# P}

$P^{\#P}$

Emil Jeřábek unterstützt Monica

Antworten:

Dies ist eine meiner Lieblingsfragen.

Fortnow hat in seiner Arbeit "Time-Space Tradeoffs for Satisfiability" gezeigt , dass korrekt in , wobei eine beliebige unbegrenzte Funktion ist. Das heißt, der nichtdeterministische Lograum ist ordnungsgemäß in der alternierenden Polynomzeit mit Alternationen enthalten. $NL$ $\Sigma_{a(n)} P$ $a(n)$ $a(n)$

Zu zeigen, dass für eine feste Konstante nicht in würde bedeuten, dass . (Um dies zu sehen, betrachten Sie das Gegenteil.) $NL$ $\Sigma_k P$ $k$ $NL \neq NP$

Es ist offen, ob . Das letzte Mal, als ich ernsthaft versuchte, dies zu beweisen, kam es zu dem Artikel "Time-Space-Kompromisse beim Zählen von NP-Lösungen mit Modulo-Ganzzahlen" . Ich habe versucht, eine Simulation für jede Sprache im Logspace zu finden, die Zeit für ein festes wenn man Zugriff auf ein Orakel zum Zählen zufriedenstellender Zuordnungen zu einer bestimmten Formel hat. (Dies würde bedeuten, dass .) Mein Ansatz hat nicht funktioniert, aber ich habe denselben Ansatz verwendet, um Zeit-Raum-Untergrenzen für die Lösung von und anderen verwandten Ergebnissen zu beweisen . $NL = P^{\#P}$ $n^k$ $k$ $LOGSPACE \neq P^{\#P}$ $Mod_6 SAT$

Uniform- ist korrekt in . Der Beweis ist in Allender, "The Permanent erfordert große, einheitliche Schwellenstromkreise" . Jede Verbesserung dieser Trennung ist offen. (Zum Beispiel ist der Nachweis von Uniform- offen, und der Nachweis von Uniform- ist ebenfalls offen.) $TC^0$ $P^{\#P}$ $NC^1 \neq P^{\#P}$ $TC^0 \neq NP$

Ryan Williams
quelle

Cool! (Übrigens, in Bezug auf Ihre letzte Nicht-klammerten Satz: Koiran und Perifel arxiv.org/abs/0902.1866 verbessert Allender Ergebnis zu Poly-size einheitliche Schaltungen der Tiefe - aber ich denke , jeder Verbesserung auf , dass offen ist ).

T C

$\mathsf{TC}$

o (\log \log n)

$o(\log \log n)$

Joshua Grochow

Ja, ich weiß auch darüber Bescheid und auch über andere Referenzen. Aber ich habe mich an eine zusammenfassende Antwort gehalten, die nicht länger als 10 Minuten dauern würde.

Ryan Williams