Sipser–Lautemann theorem explained

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 proof by Lautemann.^[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) = . 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=. 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

(|A(x)|)/(|R|) \ge 1 - (1)/(2 ^{|x|}) , then \exists t _{1,t} _{2,\ldots,t} _{|r|} , where t _{i} \in \{ 1 , 0 \} ^{|r|} such that c up _{i} A(x) ⊕ t _{i} = R.

Proof. Randomly pick t₁, t₂, ..., t_|r|. Let

S = c up _{i} A(x) ⊕ 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) ⊕ t _{1]} ⋅ \Pr [r \notin A(x) ⊕ t _{2]} … \Pr [r \notin A(x) ⊕ t _{|r|} ] \le { (1)/(2 ^{|x|}) }.

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

\Pr l [ v ee _{i} (r _{i} \notin S) r ] \le \sum _{i} (1)/(2 ^{|x|}) = (2 ^{|r|})/(2 ^{|x|}) < 1 .

Therefore

\Pr [S = R] \ge 1 - (2 ^{|r|})/(2 ^{|x|}) > 0 .

Thus there is a selection for each

t _{1,t} _{2,\ldots,t} _{|r|} such thatc up _{i} A(x) ⊕ 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 = c up _{i} A(x) ⊕ t _{i} . We have:(|S|)/(|R|) \le |r| ⋅ (|A(x)|)/(|R|) \le |r| ⋅ 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,...,t} _{|r|} \forall r \in R v ee (M(x, r ⊕ t _{i)} 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

BPP \subseteq MA \subseteq S ^{P} _{2} \subseteq \Sigma _{2} \cap \Pi _{2} (see MA, S).^{[3] [4]}

References

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