Ist bekannt, ob

Die umgekehrte Einbeziehung ist offensichtlich, ebenso wie die Tatsache, dass jede selbstreduzierbare NP-Sprache in BPP auch in RP enthalten ist. Ist dies auch für nicht selbstreduzierbare NP-Sprachen bekannt?

Wie bei den meisten Fragen der Komplexität bin ich mir nicht sicher, ob es für eine sehr lange Zeit eine vollständige Antwort geben wird. Aber wir können zumindest zeigen, dass die Antwort nicht relativierend ist: Es gibt ein Orakel, für das Ungleichheit gilt, und eines, für das Gleichheit gilt. Es ist ziemlich einfach, ein Orakel zu geben, bei dem die Klassen gleich sind: Jedes Orakel mit funktioniert (z. B. jedes Orakel, bei dem "Zufälligkeit nicht viel hilft") wird jedes Orakel, das (z. B. jedes Orakel, bei dem "Zufälligkeit viel hilft"). Es gibt viele davon, daher werde ich mich nicht um die Einzelheiten kümmern.N P ⊆ B P $\mathrm{BPP} = \mathrm{RP}$$\mathrm{NP} \subseteq \mathrm{BPP}$

Es ist etwas schwieriger, wenn auch noch recht einfach, ein Orakel zu entwerfen, für das wir . Die folgende Konstruktion ist tatsächlich etwas besser: Für jede Konstante gibt es ein Orakel, zu dem es eine Sprache in die nicht in . Ich werde es unten skizzieren. c c o R P ∩ U P R P T I M E [ 2 n c$\mathrm{RP} \subsetneq \mathrm{BPP} \cap \mathrm{NP}$$c$$\mathrm{coRP} \cap \mathrm{UP}$$\mathrm{RPTIME}[2^{n^c}]$

Wir werden ein Orakel entwerfen , das Zeichenfolgen der Form , wobei eine Bit-Zeichenfolge ist, ein einzelnes Bit ist und eine Bitzeichenfolge der Länge . Wir werden auch eine Sprache , die von einer -Maschine und einer -Maschine wie folgt entschieden wird:( x , b , z ) x n b z 2 n c L A c o R P U $A$$(x,b,z)$$x$$n$$b$$z$$2n^c$$L^A$$\mathrm{coRP}$$\mathrm{UP}$

• Der Maschine, an Eingang , Vermutungen mit der Länge zufällig, Abfragen , und kopiert die Antwort. x z 2 | x | c ( x , 0 , z $\mathrm{coRP}$$x$$z$$2|x|^c$$(x,\mathtt{0},z)$
• Die - Maschine, bei der Eingabe , Vermutungen mit der Länge , Abfragen , und kopiert die Antwort. x z 2 | x | c ( x , 1 , z $\mathrm{UP}$$x$$z$$2|x|^c$$(x,\mathtt{1},z)$

Damit die oben genannten Maschinen tatsächlich ihre Versprechen erfüllen, benötigen wir , um einige Eigenschaften zu erfüllen. Für jedes muss eine dieser beiden Optionen der Fall sein:$A$$x$

• Option 1: höchstens die Hälfte der Möglichkeiten hat und Null Möglichkeiten haben . (In diesem Fall ist )( x , 0 , z ) ∈ A z ( x , 1 , Z ) ∈ A x ∉ L $z$$(x,\mathtt{0},z) \in A$ $z$$(x,\mathtt{1},z) \in A$$x \not\in L^A$
• Option 2: Jede Wahl hat und genau eine Wahl hat . (In diesem Fall )( x , 0 , z ) ≤ A z ( x , 1 , z ) ≤ A x ≤ L $z$$(x,\mathtt{0},z) \in A$ $z$$(x,\mathtt{1},z) \in A$$x \in L^A$

Unser Ziel wird es sein, zu spezifizieren , das diese Versprechen erfüllt, so dass gegen jede Maschine diagonalisiert . Um zu versuchen, diese bereits lange Antwort kurz zu halten, werde ich die Orakelbaumaschinen und viele unwichtige Details fallen lassen und erklären, wie man gegen eine bestimmte Maschine diagonalisiert. Fix eine randomisierte Turing Maschine, und lassen ein Eingang sein , so dass wir die volle Kontrolle über die Auswahl haben 's und ist so , dass . Wir werden auf brechen .L A R P T I M E [ 2 n c ] M x b z ( x , b , z ) ∈ A M $A$$L^A$$\mathrm{RPTIME}[2^{n^c}]$$M$$x$$b$$z$$(x,b,z) \in A$$M$$x$

• Fall 1: Angenommen, es gibt eine Möglichkeit, die so auszuwählen , dass die erste Option seines Versprechens erfüllt und eine Zufallsauswahl hat, die akzeptiert. Dann werden wir für diese Auswahl festlegen. Dann kann das Versprechen nicht gleichzeitig erfüllen und ablehnen . Dennoch . Wir haben also gegen diagonalisiert .A M A M R P x x ∉ L A$z$$A$$M$$A$$M$$\mathrm{RP}$$x$$x \not\in L^A$$M$

• Fall 2: Nehmen Sie als nächstes an, dass der vorherige Fall nicht geklappt hat. Wir werden nun zeigen, dass dann gezwungen werden kann, entweder das Versprechen zu brechen oder eine Auswahl von abzulehnen, die die zweite Option seines Versprechens erfüllt. Diese diagonalisiert gegen . Wir werden dies in zwei Schritten tun:R P A $M$$\mathrm{RP}$$A$$M$

  1. Zeigen Sie, dass für jede feste Auswahl der Zufallsbits von ablehnen muss, wenn alle seine Abfragen des Formulars in und alle seine Abfragen des Formulars ist nicht in .M M ( x , 0 , z ) A ( x , 1 , z ) $r$$M$$M$$(x,\mathtt{0},z)$$A$$(x,\mathtt{1},z)$$A$
  2. Zeigen Sie, dass wir eine Antwort von für eine Auswahl von ohne die Akzeptanzwahrscheinlichkeit von wesentlich zu beeinflussen.A z $(x,\mathtt{1},z)$$A$$z$$M$

  Wenn wir ab Schritt 1 mit beginnen , ist die Akzeptanzwahrscheinlichkeit von tatsächlich Null. erfüllt die zweite Option seines Versprechens nicht ganz, aber wir können dann ein einzelnes Bit wie in Schritt 2 umdrehen und es wird. Da das Umdrehen des Bits dazu führt , dass die Akzeptanzwahrscheinlichkeit von nahe Null bleibt, kann nicht gleichzeitig akzeptieren und das Versprechen erfüllen .M A M M x R $A$$M$$A$$M$$M$$x$$\mathrm{RP}$

Es bleiben die beiden Schritte in Fall 2 zu argumentieren:

1. Fix eine Auswahl von zufälligen Bits für . Nun Simulieren unter Verwendung als die Zufälligkeit und die Beantwortung der Anfragen , so dass und . Beachten Sie, dass höchstens Abfragen macht. Da es Auswahlmöglichkeiten von , können wir die nicht erfassten Auswahlmöglichkeiten von festlegen , dass sie haben und immer noch die erste Option von erfüllt sein Versprechen. Da Fall 2 für nicht funktionieren konnte , bedeutet diesM M r ( x , 0 , z ) ∈ A ( x , 1 , Z ) ∉ A M 2 n c 2 2 n c z z ( x , 0 , z ) ∉ A A M M A R A ( x , 0 , z ) ∈ A ( x , 1$r$$M$$M$$r$$(x,\mathtt{0},z) \in A$$(x,\mathtt{1},z) \not\in A$$M$$2^{n^c}$$2^{2n^c}$$z$$z$$(x,\mathtt{0},z) \not\in A$$A$$M$$M$muss bei all seinen Zufallsentscheidungen in Bezug auf und insbesondere bei ablehnen . Daraus folgt, dass wenn wir auswählen , um und für jede Wahl von , dann für jede Wahl von Zufallsbit , verwirft zum relativen .$A$$r$$A$$(x,\mathtt{0},z) \in A$z r M $(x,\mathtt{1},z) \not\in A$$z$$r$$M$$A$

2. Angenommen, für jedes der Bruchteil der Zufallsbits, für die Abfragen mindestens . Dann beträgt die Gesamtzahl der Abfragen mindestens . Andererseits macht höchstens Abfragen über alle seine Zweige hinweg, ein Widerspruch. Daher gibt es eine Wahl von so dass der Bruchteil der Zufallsbits, für die Abfragen kleiner als 1/2 ist. Das Umdrehen des Wertes von in dieser Zeichenfolge beeinflusst daher die Akzeptanzwahrscheinlichkeit von um weniger als .M ( x , 1 , Z ) 1 / 2 2 2 n c 2 2 n c / 2 M 2 2 n c 2 n c z M ( x , 1 , Z ) A M 1 /$z$$M$$(x,\mathtt{1},z)$$1/2$$2^{2n^c} 2^{2^{n^c}}/2$$M$$2^{2^{n^c}} 2^{n^c}$$z$$M$$(x,\mathtt{1},z)$$A$$M$$1/2$

Nein, es ist nicht bekannt. Dies ist möglicherweise nicht der überzeugendste Beweis, aber werfen Sie einen Blick auf diese Google-Suche .