[Solved]: Understanding the Sipser-Gacs-Lautemann theorem

Problem Detail: 

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.

Asked By : Vitalij Zadneprovskij

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29990

3.2K people like this

 Download Related Notes/Documents