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

12

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

F1: Was ist mit und - sind diese bekanntermaßen streng?LPHLP#P

F2: Wenn nein, gibt es eine etablierte Klasse die und für die nicht bekannt ist, ob die Einbeziehung streng ist?CP#PLC

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

Łukasz Grabowski
quelle
2
Ich denke für Q2 meinst du streng in PSPACE enthalten?
Sasho Nikolov
5
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
Kaveh
4
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. N C 1 C P # P P S P A C ELNC1CP#PPSPEINCE
Joshua Grochow
Ihr Fragentitel lautet "Größte Klasse". Meinst du nicht "kleinste Klasse"?
Shaull
4
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. P # PEINC0[6]P#P
Emil Jeřábek unterstützt Monica

Antworten:

7

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.Σ a ( n ) P a ( n ) a ( n )NLΣein(n)Pein(n)ein(n)

Zu zeigen, dass für eine feste Konstante nicht in würde bedeuten, dass . (Um dies zu sehen, betrachten Sie das Gegenteil.)k P k N L n PNLΣkPkNLNP

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#PnkkLOGSPACEP#PMod6SAT

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.)TC0P#PNC1P#PTC0NP

Ryan Williams
quelle
3
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 ).TCo(loglogn)
Joshua Grochow
1
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