patternMinor
Adleman's theorem to $\mathsf{P=BPP}$
Viewed 0 times
mathsftheorembppadleman
Problem
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?
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?
Solution
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}$.
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}$.
Context
StackExchange Computer Science Q#41820, answer score: 2
Revisions (0)
No revisions yet.