# Adleman's theorem to $\mathsf{P=BPP}$

Adleman's theorem gives $$\mathsf{BPP\subseteq P/Poly}.$$

Why is this theorem considered progenitor to derandomization conjecture that $\mathsf{P=BPP}$?

Does it mean Adleman's result could be considered as evidence $$\mathsf{BPP\subseteq P/Log}$$ is a realistic possibility?

Anaalogously, does it mean $$\mathsf{NP\subseteq P/Poly}$$ could be considered as evidence $$\mathsf{NP\subseteq P/Log}$$ is a realistic possibility?

Is there a satifactory answer without considering Impagliazzo-Wigderson's conditional $\mathsf{P=BPP}$ result?

• The result you mention means that nonuniformly, BPP derandomizes. The stronger conjecture is that this happens uniformly as well. I suppose that if the nonuniform version wasn't so easy to prove, then experts would not believe the much stronger conjecture. – Louis Apr 25 '15 at 8:02
• @Louis Does it mean if $\mathsf{NP\subseteq P/Poly}$, then it is evidence $\mathsf{NP=P}$? – T.... Apr 25 '15 at 17:48
• I'm not a complexity theorist, but I would note that a huge amount of effort (mostly before Razborov-Rudich) went into trying to prove that NP is not in P/poly as a way of separating P from NP. – Louis Apr 25 '15 at 19:03

First of all, $\mathrm{NP}\subset\mathrm{P}/log$ would imply that $\mathrm{NP}=\mathrm{P}$ (try all possible log-long advice to search for a satisfying assignment in SAT problem).

Second, the situation for $\mathrm{BPP}$ is more complicated. Since $\mathrm{BPP}$ languages do not have short certificate, one cannot hope to deduce that $\mathrm{BPP}=\mathrm{P}$ from $\mathsf{BPP\subset P/}log$.

What we can deduce from $\mathsf{BPP\subset P/}log$ is that $\mathsf{BPP\cap NP=BPP\cap co}$-$\mathsf{NP=RP=co}$-$\mathsf{RP=P}$. That is, the part of $\mathsf{BPP}$ inside $\mathsf{NP\cup co}$-$\mathrm{NP}$ is just $\mathrm{P}$.