6
$\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?

Improve this question
$\endgroup$
3
  • 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
    Commented Apr 25, 2015 at 8:02
  • $\begingroup$ @Louis Does it mean if $\mathsf{NP\subseteq P/Poly}$, then it is evidence $\mathsf{NP=P}$? $\endgroup$
    – Turbo
    Commented Apr 25, 2015 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
    Commented Apr 25, 2015 at 19:03

1 Answer 1

Reset to default
2
$\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}$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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