Czy

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

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

Co myślisz?

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:

1. RP w Wikipedii
2. Uwagi na temat algorytmów losowych (pdf)
3. RP w zoo złożoności

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