# Why doesn't this put $BPP$ in $NP$?

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

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.

• So if $t_i$ are independent of $x$ what does this give? – 1.. Dec 31 '17 at 17:30
• 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. – Yuval Filmus Dec 31 '17 at 17:32
• 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. – 1.. Dec 31 '17 at 17:34
• 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. – Yuval Filmus Dec 31 '17 at 17:36
• 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$)? – 1.. Dec 31 '17 at 17:45