Sipser–Lautemann theorem


In computational complexity theory, the Sipser–Lautemann theorem or Sipser–Gács–Lautemann theorem states that bounded-error probabilistic polynomial 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. 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. 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. Without loss of generality, a machine M ∈ BPP with error ≤ 2−|x| can be chosen. 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 =. The key to the proof is to note that when x ∈ L, A is very large and when x ∉ L, A is very small. By using bitwise parity, ⊕, a set of transforms can be defined as A ⊕ 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 Σ2 sentence and a Π2 sentence can be generated that is true if and only if x ∈ L.

Lemma 1

The general idea of lemma one is to prove that if A 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:
Proof. Randomly pick t1, t2,..., t|r|. Let .
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

The previous lemma shows that A 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

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 ⊕ ti.
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

The theorem can be strengthened to .