[Solved]: Consequences of $NP=coNP=BPP=RP$

Problem Detail: 

What is complexity theoretic implication of following possibilities - $NP=coNP=BPP=RP$ or $coNP\neq NP=BPP=RP$ (consensus is these seem impossible)?

Asked By : Turbo

Answered By : Luke Mathieson

Unless I'm missing something obvious (it is getting late here), the second isn't possible - $BPP = coBPP$, so $NP=BPP \rightarrow NP = coBPP \rightarrow NP = coNP$.

In the first case, some of the consequences would be:

• "Feasible" algorithms for $NP$-complete problems, for at least the randomised version of feasible.
• $PH \subseteq NP$
• Unless $P = NP$, adding randomness adds computational power.
• Strong pseudorandom number generators do not exist (nor do one way functions). (we would need $BPP = P$ for them to exist, but that would imply $P=NP$, in which case they don't).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40976

3.2K people like this

 Download Related Notes/Documents