New answers tagged derandomization
11
This is not known, but as domotorp stated, it is believed not to be the case. First, note that $\mathsf{P} = \mathsf{BPP}$ doesn't say that randomness isn't useful in any context, just in the context of poly-time decision problems. For example, just assuming $\mathsf{P} = \mathsf{BPP}$ is already not known to imply that $\mathsf{AM} = \mathsf{NP}$ (and the ...
2
No, but I don't know what would count as a proof. People conjecture P=BPP and IP$\ne$NP, if that is good enough.
Top 50 recent answers are included
