5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Виталий Олегович Sep 14 '14 at 16:59
  • $\begingroup$ Sorry, I misread your formula. Also, you have a typo in the second line, $u_1$ for $u_i$. $\endgroup$ – Yuval Filmus Sep 14 '14 at 17:02
  • $\begingroup$ It is somewhat difficult to answer your question without you mentioning the claims about sets of binary strings. $\endgroup$ – Yuval Filmus Sep 14 '14 at 17:21
  • $\begingroup$ 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$? $\endgroup$ – Yuval Filmus Sep 14 '14 at 17:25
  • $\begingroup$ @YuvalFilmus sorry, the previous form of my question contained many errors, I have corrected them and added information about the claims about binary strings. $\endgroup$ – Виталий Олегович Sep 14 '14 at 18:08
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. What I don't understand is how the translations preserve the original random strings and how can a small set of strings cover all possible random strings. $\endgroup$ – Виталий Олегович Sep 14 '14 at 18:10
  • $\begingroup$ @VitalijZadneprovskij it's not a small set of strings but of translates. That it covers all random strings is the content of one of the lemmas you state. $\endgroup$ – Yuval Filmus Sep 14 '14 at 18:19
  • $\begingroup$ But I don't understand how and why. This is the reason why I posted my question here. $\endgroup$ – Виталий Олегович Sep 14 '14 at 18:47
  • $\begingroup$ @VitalijZadneprovskij First amplify your algorithm, reducing the error to $2^{-n} $. Then apply the lemma you state. This is just syntactic manipulation. $\endgroup$ – Yuval Filmus Sep 14 '14 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.