* Last revised 4/29/2010*

In this lecture, we first continue to talk about polynomial hierarchy. Then we prove the Gács-Sipser-Lautemann theorem that BPP is contained in the second level of the hierarchy.

**1. The hierarchy **

Definition 1 (Polynomial hierarchy)iff there are polynomials and a polynomial time computable function such thatiff there are polynomials and a polynomial time computable function such that

For clarity, we omitted the conditions that each string must be of polynomial length .

One thing that is easy to see is that . Also, note that, for all , , , , . This can be seen by noticing that the predicates do not need to “pay attention to” all of their arguments, and so a statement involving quantifiers can “simulate” a statement using less than quantifiers.

Theorem 2Suppose . Then .

*Proof:* For any language , we have that there exist polynomials and a polynomial time computable function F such that

where we did not explicitly stated the conditions . Let us look at the right hand side of the equation. What is following is a statement. Thus, there is a such that

Under the assumption that , we have , which means that there are polynomials and a polynomial time computable such that

where we omitted the conditions . So now we can show that

And so .

Now notice that if and are two complexity classes, then implies . Thus, we have . So we have .

**2. **

This result was first shown by Sipser and Gács. Lautemann gave a much simpler proof which we give below.

Lemma 3If is inBPPthen there is an algorithm such that for every ,

where the number of random bits and runs in time .

*Proof:* Let be a **BPP** algorithm for . Then for every ,

and uses random bits where .

Do repetitions of and accept if and only if at least executions of accept. Call the new algorithm . Then uses random bits and

We can then find with such that .

Theorem 4.

*Proof:* Let be in **BPP** and as in the claim. Then we want to show that

where is the number of random bits used by on input .

Suppose . Then

So

So a sequence exists, such that .

Conversely suppose . Then fix a sequence . We have

So

So for all there is a such that .

Thanks Luca for these notes! They’re very informative and I like learning a theorem or two from you every day.

A minor typographical error: In the last equality, I think you meant to put $$\mathop{\mathbb P}_{z} \left(\bigvee_i A(x,y_i\oplus z) = 0\right)$$ (missing the equals 0).