Oracle Ergebnisse auf P vs BPP

10

Sei ein EXP-Komplettproblem. Dann . $A$ $P^A = NP^A$

Sei ein Orakel, das die Abfragen berücksichtigt, die (ein TM in P) stellen wird, und wir können . $B$ $M$ $P^B \neq NP^B$

Frage: Haben wir ähnliche Orakelergebnisse für P gegen BPP?

cc.complexity-theory oracles relativization Kaveh
quelle

2

Ja, aber ich bin nicht sicher, ob ich ein Zitat finden kann. (Nun, der erste Teil ist einfach, geben Sie beiden Klassen ein Orakel für ein EXP-vollständiges Problem.)

Robin Kothari

3

Wenn Sie von PCP Einstellung denken als Verifizierer Oracle Zugriff auf Prover mit (wo das Orakel Abfrage

die zurückkehren würde

Bit des Beweises) , dann wissen wir , dass , wenn Sie Verifizierer erlauben eine BPP Maschine mit sein

Zufälligkeit und

- Abfragen dann wird die Klasse von Sprachen berechnet ist

und wenn der Verifizierer eine P - Maschine ist (dh keine Zufälligkeit) mit

(auch mit

) fragt dann die Klasse der Sprachen berechnete

. Dies zeigt nicht ein Orakel Trennung , es sei denn

. Aber nur ein Beispiel, wo Orakel Zugang zu

i

$i$

i^{t h}

$i^{th}$

\log n

$\log n$

3

$3$

N P

$NP$

3

$3$

\log n

$\log n$

P

$\bf P$

P \neq N P

$\bf P \neq \bf NP$

"scheint" mächtiger.

B P P

$\bf BPP$

Sajin Koroth

\oplus P = N P = E X P

$\oplus P=NP=EXP$

A

$A$

E X P

$EXP$

N P^{A} = N P^{\oplus P} = \oplus P^{\oplus P} = \oplus P = N P = E X P \neq P

$NP^A=NP^{\oplus P}=\oplus P^{\oplus P}=\oplus P=NP=EXP\neq P$

P^{A} = N P^{A} ⟹ P^{\oplus P} = N P = \oplus P

$P^A=NP^A\implies P^{\oplus P}=NP=\oplus P$

P \neq N P

$P\neq NP$

13

Ich hatte eine vage Erinnerung daran, dass ich eine ausgezeichnete Referenz für solche Orakeltrennungen kannte. Ich habe es endlich gefunden.

Eine gute Referenz für Orakeltrennungen (für Klassen zwischen P und PSPACE) ist das folgende Papier :

Vereshchagin, NK (1994), "RELATIVISIERBARE UND NICHTRELATIVIERBARE THEOREME IN DER POLYNOMENTHEORIE DER ALGORITHMEN", Russische Akademie der Wissenschaften. Izvestiya Mathematics 42 (2): 261

Das Papier zeigt (oder zitiert) eine Orakeltrennung zwischen fast jedem Klassenpaar, das Sie zwischen P und PSPACE interessieren könnte (z. B. Klassen wie P, RP, BPP, UP, FewP, NP, MA, AM) , andere Ebenen von PH, PH, IP, PSPACE usw.).

Zum Beispiel zeigt Satz 8 ein Orakelproblem in coRP, das nicht in NP ist. Da (relativ zu allen Orakeln) coRP in BPP enthalten ist und NP P enthält, erhalten wir in BPP ein Orakelproblem, das nicht in P enthalten ist.

$\text{P}^A = \text{BPP}^A$

Robin Kothari
quelle

Hier ist der kostenlose Download-Link von Citeseer Citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1232

Marcos Villagra

Wenn Sie jedoch die Vollversion erhalten können, würde ich dies stattdessen empfehlen. Die Citeseer-Version hat keine Zahlen und daher fehlt ein schönes Einschlussdiagramm für Komplexitätsklassen (Abb. 1).

Robin Kothari

8

Der Komplexitätszoo ist dein Freund! Wie Robin sagte, haben Sie die halbe Antwort: Jedes EXP-vollständige Problem kollabiert NP zu P, und daher konstruierte BPP zu P. Buhrman und Fortnow ein Orakel, relativ zu dem P = RP, aber BPP nicht gleich P. Dies ist mehr als was du verlangt hast; Ich vermute, es gibt einfachere Konstruktionen, die P von RP und BPP trennen.

Sasho Nikolov
quelle

6

Eine schöne Beschreibung eines Orakels, das P und BPP trennt, gibt Greg Kuperberg in einem der Kommentare dieses interessanten Blogposts , in dem Terence Tao Turingmaschinen mit Orakeln und Komplexitätsergebnissen in Bezug auf Orakel in Form einer Allegorie beschreibt.

Alessandro Cosentino
quelle

1

das ist eine coole Beschreibung :)

Sasho Nikolov

-1

Bennett & Gill geben Orakel für beide Fälle: http://epubs.siam.org/doi/abs/10.1137/0210008

Luke Mathieson
quelle

Geben sie ein Orakel, um BPP von P zu trennen? Ich konnte einen solchen Anspruch in der Zeitung nicht finden.

Robin Kothari

Ich hatte das gedacht, leider bin ich nicht in meinem Büro und habe keinen Zugang zum PDF. Ich muss später nachsehen.

Luke Mathieson

B P P^{A} = P^{A}

$BPP^{A} = P^{A}$

Oracle Ergebnisse auf P vs BPP

Antworten: