User:Daverobe/SGL

Overview

The Sipser-Gacs-Lautemann Theory is a notable theory in the Computational Complexity subfield of Computer Science that proves that BPP, bounded-error probabilistic polynomial time, is contained in the polynomial time hierarchy, and more specifically Σ₂ ∩ Π₂.

Proof

The proof works as follows. 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.) Michael Sipser's version of the proof works by defining a Σ₂∩Π₂ sentence that is equivalent to stating that x is in the language, L, defined by M.

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 corollary).

Lemma 2

The previous lemma shows that A(x) can cover every possible point in the space using a finite set of translations. Complimentary to this, for $x\notin L$ only a small fraction of the space is covered by A(x). Therefore the set of random strings r causing M(x,r) to accept cannot be generated by a small set of vectors t_i.

$R=\cup _{i}A(x)\oplus t_{i}$

R is the set of all accepting random strings, exclusive-or'd with vectors t_i.

${\frac {|A(x)|}{|R|}}\leq {\frac {1}{2^{|x|}}}\implies \neg \exists t_{1},t_{2},...,t_{|r|}$

This states that there are many more translated strings than original random strings so that there is no set of translations to cover R.

Corollary

An important corollary of this theory shows that the result of the proof can be expressed as a Σ₂ or Π₂ sentence, as follows.

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

That is, x is in language L 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 compliment, this proves BPP ∈ Σ₂∩Π₂