Wann hört die Randomisierung auf, in PSPACE zu helfen?

12

Es ist bekannt, dass das Hinzufügen einer Randomisierung mit begrenzten Fehlern zu PSPACE keine zusätzliche Leistung bringt. Das heißt, BPPSAPCE = PSPACE.

Es ist bekanntlich nicht bekannt , ob P = BPP, aber es ist bekannt , dass .BPPΣ2Π2

Somit ist es möglich (obwohl angenommen wird, dass es falsch ist), dass die Addition der Wahrscheinlichkeit zu P die Ausdruckskraft erhöht.

Meine Frage ist, ob wir die Grenze zwischen P und PSPACE kennen (oder nachweisen), bei der das Hinzufügen von Randomisierung nicht mehr die Macht erhöht.

Speziell,

Gibt es irgendwelche Probleme, von denen bekannt ist, dass sie in (bzw. B P Π i ) sind, von denen nicht bekannt ist, dass sie in Σ i (bzw. Π i ) sind? Und ähnlich für B P P H vs P H ?BPΣichBPΠichΣichΠichBPPHPH

Shaull
quelle
6
BPPH = PH. xxxxxxxxxxxxx
Emil Jeřábek unterstützt Monica am
@ EmilJeřábek - danke, hast du eine Referenz für dieses Ergebnis?
Shaull
7
Dies ist nur eine Relativierung des Gács-Sipser-Lautemann-Theorems.
Emil Jeřábek unterstützt Monica am
4
Obwohl für eine festere Bindung, ist es besser , die Aufnahme zu relativieren , das verursacht B P Σ P iΠ P i + 1 (für i 1 ) und dually B P Π P iΣ P i + 1 . EINMΠ2PBPΣichPΠich+1Pich1BPΠichPΣich+1P
Emil Jeřábek unterstützt Monica am

Antworten:

9

Die Prämisse Ihrer Frage "Wann hört die Randomisierung auf, innerhalb von helfen?" Ist schwierig, weil sie nahelegt, dass die Rechenklassen X so sind, dass P X P S P A C E eine Art Linear bilden Hierarchie, wenn dies nicht offensichtlich ist.PSPACEXPXPSPACE

Wir können dies durch Vergleiche zwischen der Polynomhierarchie und den Zählklassen veranschaulichen. Wie Emil Jeřábek in den Kommentaren angibt, durch Relativierung derAM& Pgr; p 2

BPΣipΠi+1pandBPΠipΣi+1p
AMΠ2p; und damit . Auf der anderen Seite, Toda Theorem zeigt , daß P H B P & xoplus; P . Wenn Sie annehmen, dass "die Randomisierung aufgehört hat, Leistung hinzuzufügen, bis Sie auf P aufsteigenBPPH=PH
PHBPP.
“, dann werden Sie dasweil zu vermutenversuchen P H B P P , vielleicht inTat B P P = PPHPHBPPBPP=P. Aber ich weiß nicht , dass jemand diese Vermutungen, oder sogar , dass (das eine notwendige Folge wäre); Ich denke, dass jedes Ergebnis dieser Art als großer Durchbruch angesehen werden würde.PHP

Wenn Sie sich nur um die Polynomhierarchie und allgemeiner (um auf zu skalieren ) quantifizierte Boolesche Formeln kümmern, können Sie natürlich eine Art lineare Antwort auf Ihre Frage extrahieren - in diesem Fall lauten die Kommentare von Emil Eine Antwort, die so vollständig ist, wie Sie wahrscheinlich erhalten werden.PSPEINCE

Niel de Beaudrap
quelle
Vielen Dank! Ich dachte tatsächlich mehr an die Polynom-Hierarchie als an andere Klassen. Tatsächlich ergibt sich diese Frage aus dem Studium der Einschränkungen der zeitlichen Logik, so dass eine Art Hierarchie zwischen ihnen besteht und Zählklassen weniger relevant sind.
Shaull
1
Vielleicht möchten Sie dann eine genauere Version Ihrer Frage finden und es erneut versuchen. :-)
Niel de Beaudrap
3
In Bezug auf den Punkt "Randomisierung hat aufgehört, Leistung zu addieren": Wir haben auch , aber dies impliziert nicht B PC = C für alle Klassen CB P PBPBPP=BPPBPC=CCBPP .
Emil Jeřábek unterstützt Monica
@Emil: Sicher, obwohl eine faire Beschwerde sein kann, dass es dort bereits Zufälligkeiten gibt. Dies wirft die Frage auf, ob man (für jede Klasse, wie auch immer angegeben) erkennen kann, ob sie bereits "Zufälligkeit" enthält, aber das ist ein viel komplizierterer Fischkessel.
Niel de Beaudrap