Würde

10

Wenn ist, kollabiert die Hierarchie auf ihre zweite Ebene (nach dem Karp-Lipton-Theorem). Aber was ist mit und ? $\sf RP = NP$ $\sf NP$ $\sf coNP$

Ich habe versucht zu beweisen, dass in (die andere Richtung ist trivial, wenn ), aber ohne Erfolg, und ich bin mir nicht einmal sicher, ob es wahr ist. $\sf BPP$ $\sf NP$ $\sf RP = NP$

Was denken Sie?

complexity-theory complexity-classes probabilistic-algorithms Robert777
quelle

Ich glaube nicht, dass es einen bestimmten formalen Grund dafür gibt (aber auch keinen Grund, dies nicht zu tun). Kurz gesagt, ich glaube, es ist offen.

Luke Mathieson

Der bedingungslose Beweis von

ist ein offenes Problem.

B P P \subseteq N P

$\mathbb{BPP} \subseteq \mathbb{NP}$

Chazisop

3

Wenn wir beweisen können, dass RP unter Komplement geschlossen ist, können wir sagen, dass wenn RP = NP ist, dies NP = Co-NP impliziert.

Wir wissen aber nicht, ob RP = Co-RP ist oder nicht. BPP = P kann unter einigen vernünftigen Annahmen nachgewiesen werden, aber RP BPP. $\subseteq$

Wenn wir zeigen, dass RP = BPP ist, ist Ihre Aussage korrekt.

Verweise:

Pragya
quelle

oder dass RP = ZPP.

1

Verwenden Sie in Cook und Krajicek,Folgen der Beweisbarkeit vonNP $\mathsf{RP=NP\implies NP\subseteq P/poly}$ $\,\subseteq\,$ P / poly (Journal of Symbolic Logic, 72 (4): 1353–71, 2007; PS ).

T ....
quelle

Würde

Antworten: