5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Louis Apr 25 '15 at 8:02
  • $\begingroup$ @Louis Does it mean if $\mathsf{NP\subseteq P/Poly}$, then it is evidence $\mathsf{NP=P}$? $\endgroup$ – Turbo Apr 25 '15 at 17:48
  • $\begingroup$ 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. $\endgroup$ – Louis Apr 25 '15 at 19:03
1
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.