Czy

10

Jeśli hierarchia zapada się na swój drugi poziom (według twierdzenia Karpa-Liptona). Ale co z i ? $\sf RP = NP$ $\sf NP$ $\sf coNP$

Starałem się udowodnić, że zawarty jest w (drugi kierunek jest trywialne, jeśli ), ale bez skutku, a nie jestem nawet pewien, że to prawda. $\sf BPP$ $\sf NP$ $\sf RP = NP$

Co myślisz?

complexity-theory complexity-classes probabilistic-algorithms

— Robert777
źródło

Nie sądzę, aby istniał jakiś konkretny formalny powód, aby tak myśleć (ale nie ma żadnego powodu, aby tego nie robić). Krótko mówiąc, uważam, że jest otwarty.

— Luke Mathieson

Udowodnienie bezwzględnego udowodnienia

jest otwartym problemem.

B P P \subseteq N P

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

— chazisop,

3

Jeśli uda nam się udowodnić, że RP jest zamknięte pod dopełnieniem, możemy powiedzieć, że jeśli RP = NP, oznacza to, że NP = Co-NP.

$\subseteq$

Jeśli pokażemy, że RP = BPP, twoje oświadczenie będzie poprawne.

Bibliografia:

— Pragja
źródło

lub że RP = ZPP.

1

$\mathsf{RP=NP\implies NP\subseteq P/poly}$ $\,\subseteq\,$ P / poli (Journal of Symbolic Logic, 72 (4): 1353–71, 2007; PS ).

— T ....
źródło