Beispiel für etwas, das sich für generische und zufällige Orakel unterscheidet?

Sei $G$ ein generisches Orakel im Sinne der Kategorie Cohen / Baire. Sei $R$ ein zufälliges Orakel.

Gibt es Komplexitätsklassen A und B mit

A^{G} = B^{G} and A^{R} \neq B^{R}

$\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^R$ oder umgekehrt,

A^{G} \neq B^{G} and A^{R} = B^{R} ?

$\mathrm{A}^G\ne\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R= \mathrm{B}^R\text{?}$

Die Frage wurde von einem Kommentar von Scott Aaronson inspiriert .

cc.complexity-theory complexity-classes Bjørn Kjos-Hanssen
quelle

Antworten:

P = UP mit einem Generikum (unter der Annahme von P = PSPACE), aber sie sind relativ zu einem zufälligen Orakel getrennt.

In der anderen Richtung ist P = Promise-BPP relativ zu einem Zufall, aber getrennt zu einem Generikum. Ich kann mir keine Klasse ohne Versprechen vorstellen.

Ich kann einige Referenzen finden, wenn Sie brauchen.

$P^{NP} = S^p_2$ $S^p_2 \subseteq ZPP^{NP}$

Lance Fortnow
quelle

P = PSPACE scheint eine kühne Annahme zu sein;)

Bjørn Kjos-Hanssen

Um Björns Kommentar zu verdeutlichen: Eine andere Möglichkeit, es auszudrücken, besteht darin, zuerst ein PSPACE-Orakel zu relativieren, dann ein Generikum zu erstellen und dann P = UP zu erhalten. Es gibt also ein (relativ zu PSPACE-) generisches Orakel, das P = UP macht.

Joshua Grochow

\neq

$\neq$

Ich glaube nicht, dass wir bedingungslose Unterschiede in der Komplexitätsklasse in der obigen Form kennen (Update: siehe Lance Fortnows Antwort für ein Beispiel), aber der folgende Vergleich von generischen Orakeln mit zufälligen Orakeln kann hilfreich sein.

Ein generisches Orakel ist konstruktionsbedingt ein Orakel, das jede Eigenschaft erfüllt , die nicht durch Festlegen eines endlichen Anfangssegments ausgeschlossen werden kann. In gewissem Sinne passiert alles, was notwendigerweise möglich ist, was es sehr von einem zufälligen Orakel unterscheidet (obwohl es auch ein zufälliges Orakel unendlich oft emuliert). $Σ^0_1$

Zum Beispiel mit dem generischen Orakel (io bedeutet unendlich oft)
PSPACE - io-P
EXP - io-ZPP
EXP ^{NP -} io-BPP

Daher gibt es für jedes Problem im relativierten PSPACE einen Polynomzeitalgorithmus (unter Verwendung des Orakels), der für unendlich viele Eingabegrößen alle Instanzen dieser Größe löst (und ähnlich bei ZPP und BPP mit willkürlichem Verhalten bei "schlechten" Eingabegrößen). .

Wie das zufällige Orakel:
IP <PSPACE
Die Polynomhierarchie ist unendlich.

Jede rekursive Funktion, die in Polynomzeit mit einem generischen Orakel berechenbar ist, ist in Polynomzeit ohne das Orakel berechenbar (da das Orakel für ausreichend lange Strecken leer ist). Wenn also P <BPP ist, gilt dies auch für das generische Orakel, während für das zufällige Orakel P = BPP gilt.

Dmytro Taranovsky
quelle

Was meinst du mit = io zwischen Sprachklassen?

Kaveh

Mit "P = ioPSPACE" meinen Sie also tatsächlich PSPACE ioP? Das ist ziemlich verwirrend. Warum haben Sie das io-Präfix in die andere Klasse verschoben?

\subseteq

$\subseteq$

Emil Jeřábek

@Kaveh A = io B bedeutet, dass es eine unendliche Menge S gibt, so dass A ⊆ SB und B ⊆ SA (wobei SB analog zu io-B definiert ist). Da diese Verwendung jedoch nicht dem Standard entspricht, habe ich meine Antwort geändert, um ⊆ io

Dmytro Taranovsky

@ EmilJeřábek Ich ersetzte = io durch den Standard ⊆ io

Dmytro Taranovsky

Ich weiß, was es für Sprachen bedeutet, ich frage, was es für Sprachklassen bedeutet. io-C macht Sinn für eine Klasse C, = io als Beziehung scheint keinen Sinn zu ergeben, wie Sie ursprünglich geschrieben haben.

Kaveh