Sipser–Lautemann theorem

Here we present the proof by Lautemann. 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).

The general idea of lemma one is to prove that if A(x) covers a large part of the random space $R=\; \backslash \{\; 1,0\; \backslash \}\; ^$

:If $\backslash frac$

Proof. Randomly pick t₁, t₂, ..., t_|r|. Let $S=\backslash bigcup\_i\; A(x)\backslash oplus\; t\_i$ (the union of all transforms of A(x)).

So, for all r in R,

:$\backslash Pr\; [r\; \backslash notin\; S]\; =\; \backslash Pr\; [r\; \backslash notin\; A(x)\; \backslash oplus\; t\_1]\; \backslash cdot\; \backslash Pr\; [r\; \backslash notin\; A(x)\; \backslash oplus\; t\_2]\; \backslash cdots\; \backslash Pr\; [r\; \backslash notin\; A(x)\; \backslash oplus\; t\_$

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

:$\backslash Pr\; \backslash Bigl[\; \backslash bigvee\_i\; (r\_i\; \backslash notin\; S)\backslash Bigr]\; \backslash le\; \backslash sum\_i\; \backslash frac\{1\}\{2^$

Therefore

:$\backslash Pr\; [S\; =\; R]\; \backslash ge\; 1\; -\; \backslash frac\{2^$

Thus there is a selection for each $t\_1,t\_2,\backslash ldots,t\_$

:$\backslash bigcup\_i\; A(x)\; \backslash oplus\; t\_i\; =\; R.$

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=\backslash bigcup\_i\; A(x)\backslash oplus\; t\_i$. We have:

:$\backslash frac$

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

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

:$x\; \backslash in\; L\; \backslash iff\; \backslash exists\; t\_1,t\_2,\backslash dots,t\_$

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 ⊆ Σ₂ ∩ Π₂.

The theorem can be strengthened to $\backslash mathsf\{BPP\}\; \backslash subseteq\; \backslash mathsf\{MA\}\; \backslash subseteq\; \backslash mathsf\{S\}\_2^P\; \backslash subseteq\; \backslash Sigma\_2\; \backslash cap\; \backslash Pi\_2$ (see MA, S2P (complexity)).{{cite journal | title=More on BPP and the polynomial-time hierarchy | first=Ran | last=Canetti | journal=Information Processing Letters | volume=57 | number=5 | pages=237–241 | year=1996 | doi=10.1016/0020-0190(96)00016-6}}{{cite journal | year=1998 | issn=1016-3328 | journal=Computational Complexity | volume=7 | number=2 | doi=10.1007/s000370050007 | title=Symmetric alternation captures BPP | first1=Alexander | last1=Russell | first2=Ravi | last2=Sundaram | pages=152–162| citeseerx=10.1.1.219.3028 | s2cid=15331219 }}

{{DEFAULTSORT:Sipser-Lautemann theorem}}

Category:Structural complexity theory

Category:Randomized algorithms

Category:Theorems in computational complexity theory

Category:Articles containing proofs