Roy's identity

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

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

Proof

Michael Sipser's version of 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.) 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 corollary).

Lemma 1

The general idea of lemma one is to prove that if A(x) covers a large part of the random space $R=\{1,0{\}}^{\left|r\right|}$ then there exists a small set of translations that will cover the entire random space. In more mathematical language:

If $\frac{|A(x)|}{\left|R\right|}>1-\frac{1}{2^{\left|x\right|}}$, then $\mathrm{\exists }{t}_1,t_2,\dots ,t_{\left|r\right|}$, where $t_i\in \{1,0{\}}^{\left|r\right|}$ such that $\bigcup _{i}A(x)\oplus t_i=R.$

Proof. Randomly pick t₁, t₂, ..., t_|r|. Let $S=\bigcup _{i}A(x)\oplus t_i$ (the union of all transforms of A(x)).

So, for all r in R,

$\mathrm{Pr}[r\notin S]=\mathrm{Pr}[r\notin A(x)\oplus t_1]\cdot \mathrm{Pr}[r\notin A(x)\oplus t_2]\cdots \mathrm{Pr}[r\notin A(x)\oplus t_{\left|r\right|}]\le \frac{1}{2^{\left|x\right|\cdot \left|r\right|}}.$

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

$\mathrm{Pr}[\underset{i}{\bigvee }(r_i\notin S)]\le \sum _i\frac{1}{2^{\left|x\right|\cdot \left|r\right|}}=\frac{1}{2^{\left|x\right|}}<1.$

Therefore

$\mathrm{Pr}[S=R]\ge 1-\frac{1}{2^{\left|x\right|}}.$

Thus there is a selection for each $t_1,t_2,\dots ,t_{\left|r\right|}$ such that

$\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 A(x). Therefore the set of random strings causing M(x,r) to accept cannot be generated by a small set of vectors t_i.

$R=\bigcup _{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)|}{\left|R\right|}\le \frac{1}{2^{\left|k\right|}}⟹\mathrm{\neg }\mathrm{\exists }{t}_1,t_2,\dots ,t_r$

Corollary

An important corollary of the lemmas shows that the result of the proof can be expressed as a Σ₂ expression, as follows.

$x\in L⟺\mathrm{\exists }{t}_1,t_2,\dots ,t_{\left|r\right|}\mathrm{\forall }r\in R\underset{1\le i\le \left|r\right|}{\bigvee }(M(r\oplus t_i)\text{ accepts}).$

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

Lautemann's proof

Here we present the proof (due to Lautemann) that BPP ⊆ Σ₂. See Trevisan's notes for more information.

Lemma 3

Based on the definition of BPP we show the following:

If L is in BPP then there is an algorithm A such that for every x,

${\mathrm{P}\mathrm{r}}_r(A(x,r)=\text{right answer})\ge 1-\frac{1}{3m},$

where m is the number of random bits $\left|r\right|=m=|x{|}^{O(1)}$ and A runs in time $|x{|}^{O(1)}$.

Proof: Let ATemplate:' be a BPP algorithm for L. For every x, ${\mathrm{Pr}}_r(A^{\prime }(x,r)=\text{wrong answer})\le 1/3$. ATemplate:' uses mTemplate:'(n) random bits where n = |x|. Do k(n) repetitions of ATemplate:' and accept if and only if at least k(n)/2 executions of ATemplate:' accept. Define this new algorithm as A. So A uses k(n)mTemplate:'(n) random bits and

${\mathrm{P}\mathrm{r}}_r(A(x,r)=\text{wrong answer})\le 2^{-ck(n)}.$

We can then find k(n) with $k(n)=\mathrm{\Theta }(\log m^{\prime }(n))$ such that

$\frac{1}{2^{ck(n)}}\le \frac{1}{3k(n)m^{\prime }(n)}.$

Theorem 1

Proof: Let L be in BPP and A as in Lemma 3. We want to show

$x\in L⟺\mathrm{\exists }{y}_1,\dots ,y_m\in \{0,1{\}}^m\mathrm{\forall }z\in \{0,1{\}}^m\underset{i=1}{\overset{m}{\bigvee }}A(x,y_i\oplus z)=1.$

where m is the number of random bits used by A on input x. Given $x\in L$, then

$\begin{array}{rl}{\mathrm{P}\mathrm{r}}_{y_1,\dots ,y_m}(\mathrm{\exists }z& A(x,y_1\oplus z)=\dots =A(x,y_m\oplus z)=0)\\ & \le \sum _{z\in \{0,1{\}}^m}{\mathrm{P}\mathrm{r}}_{y_1,\dots ,y_m}(A(x,y_1\oplus z)=\dots =A(x,y_m\oplus z)=0)\\ & \le 2^m\frac{1}{(3m{)}^m}\\ & <1.\end{array}$

Thus

${\mathrm{P}\mathrm{r}}_{y_1,\dots ,y_m}(\mathrm{\forall }z\underset{i}{\bigvee }A(x,y_i\oplus z))=1-{\mathrm{P}\mathrm{r}}_{y_1,...,y_m}(\mathrm{\exists }zA(x,y_1\oplus z)=\dots =A(x,y_m\oplus z)=0).$

Thus $(y_1,\dots ,y_m)$ exists.

Conversely, suppose $x\notin L$. Then

${\mathrm{P}\mathrm{r}}_z(\underset{i}{\bigvee }A(x,y_i\oplus z))\le \sum _i{\mathrm{P}\mathrm{r}}_z(A(x,y_i\oplus z)=1)\le m\frac{1}{3m}=\frac{1}{3}.$

Thus

${\mathrm{P}\mathrm{r}}_z(A(x,y_1\oplus z)=\dots =A(x,y_m\oplus z)=0)=1-{\mathrm{P}\mathrm{r}}_z(\underset{i}{\bigvee }A(x,y_i\oplus z))\ge \frac{2}{3}>0.$

Thus there is a z such that $\underset{i}{\bigvee }A(x,y_i\oplus z)=0$ for all $y_1,...,y_m\in \{0,1{\}}^m.$

Stronger version

The theorem can be strengthened to $\mathsf{B}\mathsf{P}\mathsf{P}\subseteq \mathsf{M}\mathsf{A}\subseteq {\mathsf{S}}_2^P\subseteq {\mathrm{\Sigma }}_2\cap {\mathrm{\Pi }}_2$ (see MA, [[S2P (complexity)|STemplate:Su]]).

References

• M. Sipser. A complexity theoretic approach to randomness In Proceedings of the 15th ACM Symposium on Theory of Computing, 330–335. ACM Press, 1983.
• C. Lautemann, BPP and the polynomial hierarchy Inf. Proc. Lett. 17 (4) 215–217, 1983.
• Luca Trevisan's Lecture Notes, University of California, Berkeley