# 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 Σ_{2} ∩ Π_{2}.

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 Σ_{2} ∩ Π_{2}. Clemens Lautemann contributed by giving a simple proof of BPP’s membership in Σ_{2} ∩ Π_{2}, also in 1983.^{[2]} It is conjectured that in fact BPP=P, which is a much stronger statement than the Sipser–Lautemann theorem.

## Proof[edit]

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 Σ_{2} 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 Σ_{2} sentence and a Π_{2} sentence can be generated that is true if and only if *x* ∈ *L* (see conclusion).

### Lemma 1[edit]

The general idea of lemma one is to prove that if *A*(*x*) covers a large part of the random space then there exists a small set of translations that will cover the entire random space. In more mathematical language:

*If*,*then*,*where**such that*

**Proof.** Randomly pick *t*_{1}, *t*_{2}, ..., *t*_{|r|}. Let (the union of all transforms of *A*(*x*)).

So, for all *r* in *R*,

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

Therefore

Thus there is a selection for each such that

### Lemma 2[edit]

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 . We have:

because is polynomial in .

### Conclusion[edit]

The lemmas show that language membership of a language in BPP can be expressed as a Σ_{2} expression, as follows.

That is, *x* is in language *L* if and only if there exist binary vectors, where for all random bit vectors *r*, TM *M* accepts at least one random vector ⊕ *t _{i}*.

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

## Stronger version[edit]

The theorem can be strengthened to (see MA, S^{P}

_{2}).^{[3]}^{[4]}

## References[edit]

**^**Sipser, Michael (1983). "A complexity theoretic approach to randomness".*Proceedings of the 15th ACM Symposium on Theory of Computing*. ACM Press: 330–335.- ^
^{a}^{b}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*. Elsevier.**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. doi:10.1007/s000370050007. ISSN 1016-3328.