Sipser–Lautemann theorem

In computational complexity theory, the Sipser–Lautemann theorem or Sipser–Gács–Lautemann theorem states that bounded-error probabilistic polynomial (BPP) time is contained in the polynomial time hierarchy, and more specifically Σ₂ ∩ Π₂.

In 1983, Michael Sipser showed that BPP is contained in the polynomial time hierarchy.[1] Péter Gács showed that BPP is actually contained in Σ₂ ∩ Π₂. Clemens Lautemann contributed by giving a simple proof of BPP’s membership in Σ₂ ∩ Π₂, also in 1983.[2] It is conjectured that in fact BPP=P, which is a much stronger statement than the Sipser–Lautemann theorem.

Proof

Here we present the Lautemann's proof.[2] Without loss of generality, a machine M ∈ BPP with error ≤ 2^−|x| can be chosen. (All BPP problems can be amplified to reduce the error probability exponentially.) The basic idea of the proof is to define a Σ₂ sentence that is equivalent to stating that x is in the language, L, defined by M by using a set of transforms of the random variable inputs.

Since the output of M depends on random input, as well as the input x, it is useful to define which random strings produce the correct output as A(x) = {r | M(x,r) accepts}. The key to the proof is to note that when x ∈ L, A(x) is very large and when x ∉ L, A(x) is very small. By using bitwise parity, ⊕, a set of transforms can be defined as A(x) ⊕ t={r ⊕ t | r ∈ A(x)}. The first main lemma of the proof shows that the union of a small finite number of these transforms will contain the entire space of random input strings. Using this fact, a Σ₂ sentence and a Π₂ sentence can be generated that is true if and only if x ∈ L (see conclusion).

Lemma 1

The general idea of lemma one is to prove that if A(x) covers a large part of the random space $R=\{1,0\}^{|r|}$ then there exists a small set of translations that will cover the entire random space. In more mathematical language:

If

{\frac {|A(x)|}{|R|}}\geq 1-{\frac {1}{2^{|x|}}}

, then

\exists t_{1},t_{2},\ldots ,t_{|r|}

, where

t_{i}\in \{1,0\}^{|r|}

such that

\bigcup _{i}A(x)\oplus t_{i}=R.

Proof. Randomly pick t₁, t₂, ..., t_|r|. Let $S=\bigcup _{i}A(x)\oplus t_{i}$ (the union of all transforms of A(x)).

So, for all r in R,

\Pr[r\notin S]=\Pr[r\notin A(x)\oplus t_{1}]\cdot \Pr[r\notin A(x)\oplus t_{2}]\cdots \Pr[r\notin A(x)\oplus t_{|r|}]\leq {\frac {1}{2^{|x|\cdot |r|}}}.

The probability that there will exist at least one element in R not in S is

\Pr {\Bigl [}\bigvee _{i}(r_{i}\notin S){\Bigr ]}\leq \sum _{i}{\frac {1}{2^{|x|\cdot |r|}}}={\frac {2^{|r|}}{2^{|x|\cdot |r|}}}<1.

Therefore

\Pr[S=R]\geq 1-{\frac {2^{|r|}}{2^{|x|\cdot |r|}}}>0.

Thus there is a selection for each $t_{1},t_{2},\ldots ,t_{|r|}$ such that

\bigcup _{i}A(x)\oplus t_{i}=R.

Lemma 2

The previous lemma shows that A(x) can cover every possible point in the space using a small set of translations. Complementary to this, for x ∉ L only a small fraction of the space is covered by $S=\bigcup _{i}A(x)\oplus t_{i}$ . We have:

{\frac {|S|}{|R|}}\leq |r|\cdot {\frac {|A(x)|}{|R|}}\leq |r|\cdot 2^{-|x|}<1

because $|r|$ is polynomial in $|x|$ .

Conclusion

The lemmas show that language membership of a language in BPP can be expressed as a Σ₂ expression, as follows.

x\in L\iff \exists t_{1},t_{2},\dots ,t_{|r|}\,\forall r\in R\bigvee _{1\leq i\leq |r|}(M(x,r\oplus t_{i}){\text{ accepts}}).

That is, x is in language L if and only if there exist $|r|$ binary vectors, where for all random bit vectors r, TM M accepts at least one random vector ⊕ t_i.

The above expression is in Σ₂ in that it is first existentially then universally quantified. Therefore BPP ⊆ Σ₂. Because BPP is closed under complement, this proves BPP ⊆ Σ₂ ∩ Π₂.

Stronger version

The theorem can be strengthened to ${\mathsf {BPP}}\subseteq {\mathsf {MA}}\subseteq {\mathsf {S}}_{2}^{P}\subseteq \Sigma _{2}\cap \Pi _{2}$ (see MA, S^P
₂).[3][4]

References

Sipser, Michael (1983). "A complexity theoretic approach to randomness". Proceedings of the 15th ACM Symposium on Theory of Computing. ACM Press: 330–335. CiteSeerX 10.1.1.472.8218.
Lautemann, Clemens (1983). "BPP and the polynomial hierarchy". Inf. Proc. Lett. 17. 17 (4): 215–217. doi:10.1016/0020-0190(83)90044-3.
Canetti, Ran (1996). "More on BPP and the polynomial-time hierarchy". Information Processing Letters. 57 (5): 237–241. doi:10.1016/0020-0190(96)00016-6.
Russell, Alexander; Sundaram, Ravi (1998). "Symmetric alternation captures BPP". Computational Complexity. 7 (2): 152–162. CiteSeerX 10.1.1.219.3028. doi:10.1007/s000370050007. ISSN 1016-3328. S2CID 15331219.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[sipser_paper-1] Sipser, Michael (1983). "A complexity theoretic approach to randomness". Proceedings of the 15th ACM Symposium on Theory of Computing. ACM Press: 330–335. CiteSeerX 10.1.1.472.8218.

[lautemann_paper-2] Lautemann, Clemens (1983). "BPP and the polynomial hierarchy". Inf. Proc. Lett. 17. 17 (4): 215–217. doi:10.1016/0020-0190(83)90044-3.

[canetti-3] Canetti, Ran (1996). "More on BPP and the polynomial-time hierarchy". Information Processing Letters. 57 (5): 237–241. doi:10.1016/0020-0190(96)00016-6.

[russell-sundaram-4] Russell, Alexander; Sundaram, Ravi (1998). "Symmetric alternation captures BPP". Computational Complexity. 7 (2): 152–162. CiteSeerX 10.1.1.219.3028. doi:10.1007/s000370050007. ISSN 1016-3328. S2CID 15331219.