From Sipser Gacs we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists t_1,\dots,t_{|r|}\forall r\in\{0,1\}^{|r|}\vee_{i\in\{1,\dots,|r|\}}M(x,r\oplus t_i)=1.$$

From Adleman we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists r\in\{0,1\}^{|r|}M(x,r)=1.$$

  1. Why is this just $BPP\subseteq P/Poly$ (looks like a derandomization to $BPP\subseteq NP$)? If Adleman's theorem just puts $BPP\subseteq P/Poly$ (because we need to find $r$) then why cannot I argue for similar reasons Sipser Gacs only puts $BPP\subseteq coNP/Poly$ (because we need to find $t_1,\dots,t_{|r|}$)?

  2. What should Adleman's theorem have looked like if it indeed showed $BPP\subseteq NP$ and what should Sipser Gacs' theorem have looked like if it indeed showed $BPP\subseteq coNP/poly$?


1 Answer 1


Adleman's theorem states that you can amplify the success probability of $M$ so that there will be a single choice for the random string $r$ that works for all $x$: $$ \exists r \forall x : x \in L(M) \Leftrightarrow M(x,r) = 1. $$ (Here $x$ goes over all inputs of length $n$, and $r$ goes over all possible random strings that $M$ requires for inputs of length $n$.)

Unfortunately, it's not clear how to find $r$, and even worse, if I give you $r$, it's not clear how to verify that it satisfies the property stated above. This is why we have to supply it as advice.

The Sipser–Gács theorem similarly states a different property from what you list. It states that if $M$ is a BPP machine then $$ \forall x \bigl(x \in L(M) \Longleftrightarrow \exists t_1,\ldots,t_{|r|} \forall r : M(x,r \oplus t_1) = 1 \lor \cdots \lor M(x,r \oplus t_{|r|}) = 1 \bigr). $$ Here the strings $t_i$ could depend on the input $x$. This is why you get $\Sigma_2^P$ or $\Pi_2^P$ rather than $\mathsf{NP}/\mathsf{poly}$ or $\mathsf{coNP}/\mathsf{poly}$.

Summarizing, you have to be careful with quantifiers when stating a theorem. Changing the order of the quantifiers could drastically change the meaning.

  • $\begingroup$ So if $t_i$ are independent of $x$ what does this give? $\endgroup$
    – Turbo
    Dec 31, 2017 at 17:30
  • $\begingroup$ Then you will get $\mathsf{coNP}/\mathsf{poly}$. But we already know that BPP is contained in $\mathsf{P}/\mathsf{poly}$, so that wouldn't advance our state of knowledge in any way. $\endgroup$ Dec 31, 2017 at 17:32
  • $\begingroup$ Ah so if $r$ depends on $x$ in Adleman's theorem then $BPP\subseteq NP$? It does not look that simple and I think I am missing something. $\endgroup$
    – Turbo
    Dec 31, 2017 at 17:34
  • $\begingroup$ In Adleman's theorem $r$ doesn't depend on $x$ because of the order of quantifiers. The order of quantifiers really matters. If we switched the quantifiers, we would get that BPP is in NP. $\endgroup$ Dec 31, 2017 at 17:36
  • $\begingroup$ Oh I see if quantifiers switched for adleman then $BPP\subseteq NP$. However 'it's not clear how to verify that it satisfies the property stated above'. Isn't it sufficient to verify for every $x$ individually? Why should you check before hand (why can't I say $r$ is the certificate for that $x$ and it still looks like $NP$)? $\endgroup$
    – Turbo
    Dec 31, 2017 at 17:45

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.