Será que implica ?

Se , a hierarquia cai para seu segundo nível (pelo teorema de Karp-Lipton). Mas e quanto a e ?$\sf RP = NP$$\sf NP$$\sf coNP$

Tentei provar que o está contido no (a outra direção é trivial se ), mas sem sucesso, e nem tenho certeza de que seja verdade.$\sf BPP$$\sf NP$$\sf RP = NP$

O que você acha?

Se conseguirmos provar que RP está fechado sob complemento, podemos dizer que, se RP = NP, isso implica NP = Co-NP.

Mas não sabemos se RP = Co-RP ou não. BPP = P pode ser provado sob algumas suposições razoáveis, mas RP BPP.$\subseteq$

Se mostrarmos que RP = BPP, sua declaração estará correta.

Referências:

1. RP na Wikipedia
2. Notas sobre algoritmos randomizados (pdf)
3. RP no zoológico da complexidade

Use em Cook e Krajicek. Consequências da possibilidade de NP P / poly (Journal of Symbolic Logic, 72 (4): 1353–71 2007; PS ).$\mathsf{RP=NP\implies NP\subseteq P/poly}$ $\,\subseteq\,$