Sipser–Lautemann theorem

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.

Contents 1 Proof 1.1 Lemma 1 1.2 Lemma 2 1.3 Conclusion 2 Stronger version 3 References Proof 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 The general idea of lemma one is to prove that if A(x) covers a large part of the random space {displaystyle R={1,0}^{|r|}} then there exists a small set of translations that will cover the entire random space. In more mathematical language: If {displaystyle {frac {|A(x)|}{|R|}}geq 1-{frac {1}{2^{|x|}}}} , then {displaystyle exists t_{1},t_{2},ldots ,t_{|r|}} , where {displaystyle t_{i}in {1,0}^{|r|}} such that {displaystyle bigcup _{i}A(x)oplus t_{i}=R.} Proof. Randomly pick t1, t2, ..., t|r|. Let {displaystyle S=bigcup _{i}A(x)oplus t_{i}} (the union of all transforms of A(x)).

So, for all r in R, {displaystyle Pr[rnotin S]=Pr[rnotin A(x)oplus t_{1}]cdot Pr[rnotin A(x)oplus t_{2}]cdots Pr[rnotin A(x)oplus t_{|r|}]leq {frac {1}{2^{|x|cdot |r|}}}.} The probability that there will exist at least one element in R not in S is {displaystyle Pr {Bigl [}bigvee _{i}(r_{i}notin S){Bigr ]}leq sum _{i}{frac {1}{2^{|x|cdot |r|}}}={frac {2^{|r|}}{2^{|x|cdot |r|}}}<1.} Therefore {displaystyle Pr[S=R]geq 1-{frac {2^{|r|}}{2^{|x|cdot |r|}}}>0.} Thus there is a selection for each {displaystyle t_{1},t_{2},ldots ,t_{|r|}} such that {displaystyle bigcup _{i}A(x)oplus 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 {displaystyle S=bigcup _{i}A(x)oplus t_{i}} . We have: {displaystyle {frac {|S|}{|R|}}leq |r|cdot {frac {|A(x)|}{|R|}}leq |r|cdot 2^{-|x|}<1} because {displaystyle |r|} is polynomial in {displaystyle |x|} . Conclusion The lemmas show that language membership of a language in BPP can be expressed as a Σ2 expression, as follows. {displaystyle xin Liff exists t_{1},t_{2},dots ,t_{|r|},forall rin Rbigvee _{1leq ileq |r|}(M(x,roplus t_{i}){text{ accepts}}).} That is, x is in language L if and only if there exist {displaystyle |r|} 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 {displaystyle {mathsf {BPP}}subseteq {mathsf {MA}}subseteq {mathsf {S}}_{2}^{P}subseteq Sigma _{2}cap Pi _{2}} (see MA, SP 2).[3][4] References ^ Sipser, Michael (1983). "A complexity theoretic approach to randomness". Proceedings of the 15th ACM Symposium on Theory of Computing. ACM Press: 330–335. CiteSeerX 10.1.1.472.8218. ^ Jump up to: 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. 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. CiteSeerX 10.1.1.219.3028. doi:10.1007/s000370050007. ISSN 1016-3328. S2CID 15331219. Categories: Structural complexity theoryRandomized algorithmsTheorems in computational complexity theory