# Understanding the Sipser-Gacs-Lautemann theorem

The class $BPP$ contains all the languages decided by a probabilistic Turing machine in polynomial time with probability of success more that 2/3 for every input.

The class $\Sigma^p_2$ contains all the languages for which there is a polinomial time Turing machine $M$ and a plynomial function $q : \mathbb{N} \rightarrow \mathbb{N}$ such that: $$x \in L \iff \exists u \in \{0,1\}^{q(|x|)} \forall v \in \{ 0,1 \}^{q(|x|)} M(u,x,v)=1$$ Define $\Pi^p_i=\{\bar{L} : L \in \Sigma^p_2 \}$

The theorem states that the class $BPP$ is contained by the intersection of $\Sigma^p_2$ and $\Pi^p_2$.

To prove the theorem it is proved that for every set $S \subseteq \{0,1\}^m$ with $|S| \leq 2^{m-n}$ and every k vectors $u_1, \ldots, u_k$ $$\bigcup_{i=1}^k(S+u_i) \neq \{0,1\}^m$$ Where $S+u = \{ x+u : x \in S \}$ and + denotes addition modulo 2 i.e. bitwise XOR.

It is also proved that for every set $S \subseteq \{0,1\}^m$ with $|S| \geq (1-2^{-n})2^m$ and every k vectors $u_1, \ldots, u_k$ $$\bigcup_{i=1}^k(S+u_i) = \{0,1\}^m$$

I don't get why this claims imply that if a language is in $BPP$, then $$\exists u_1, \ldots,u_k \in \{ 0,1 \}^m \forall r \in \{ 0,1 \}^m \bigvee_{i=1}^k M(x,r \oplus u_i) = 1$$

How does the claims about sets of binary strings imply the computation above?

What I don't understand is how the translations preserve the original random strings and how can a small set of translates cover all possible random strings.

• It seems strange to me that a formula that contains both $\exists$ and $\forall$ signs can describe NP. Usually NP is described by only $\exists$. Can you explain more how my formula describes NP? – Виталий Олегович Sep 14 '14 at 16:59
• Sorry, I misread your formula. Also, you have a typo in the second line, $u_1$ for $u_i$. – Yuval Filmus Sep 14 '14 at 17:02
• It is somewhat difficult to answer your question without you mentioning the claims about sets of binary strings. – Yuval Filmus Sep 14 '14 at 17:21
• Also, are you stating a purported normal form for languages in BPP? This is not clear from what you write. In other words, is it true that your final formula evaluates to true iff $x\in L$? – Yuval Filmus Sep 14 '14 at 17:25
• @YuvalFilmus sorry, the previous form of my question contained many errors, I have corrected them and added information about the claims about binary strings. – Виталий Олегович Sep 14 '14 at 18:08

First of all, it's not clear to me that every language of the form given by your last formula is in BPP. Fortunately, we only need the reverse direction: every language in BPP can be written in this form. This will show that BPP is contained in $\Sigma_2$. Since BPP is closed under complementation, this will complete the proof.
Start with a BPP machine with some small error probability. For appropriate $k$ (depending on the error probability), a union bound shows that the formula doesn't hold. The other direction looks more complicated, and this is probably where the other results they prove come in. Basically, you have a set of good random strings covering almost all strings, and you want to cover all of them by finitely many translates of the set. Perhaps that's what these lemmas show.
• @VitalijZadneprovskij First amplify your algorithm, reducing the error to $2^{-n}$. Then apply the lemma you state. This is just syntactic manipulation. – Yuval Filmus Sep 14 '14 at 18:54