Будет ли

Если то иерархия разрушается до своего второго уровня (по теореме Карпа-Липтона). Но как насчет N P и C O N P ?$\sf RP = NP$$\sf NP$$\sf coNP$

Я пытался доказать, что содержится в N P (другое направление тривиально, если R P = N P ), но безрезультатно, и я даже не уверен, что это правда.$\sf BPP$$\sf NP$$\sf RP = NP$

Что вы думаете?

Если мы сможем доказать, что RP замкнуто относительно дополнения, то мы можем сказать, что если RP = NP, то это означает, что NP = Co-NP.

$\subseteq$

Если мы покажем, что RP = BPP, то ваше утверждение будет правильным.

Ссылки:

1. RP в Википедии
2. Заметки о рандомизированных алгоритмах (pdf)
3. RP в зоопарке сложности

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