CS254 Lecture 5 – The Polynomial Hierarchy

Posted on by

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) {L \in \Sigma_k} iff there are polynomials {p_1, \ldots, p_k} and a polynomial time computable function {F} such that

\displaystyle x \in L \Leftrightarrow \exists y_1.\forall y_2.\;\ldots Q_k y_k. F(x,y_1,\ldots,y_k)=1 \qquad

\displaystyle {\rm where} \; Q_k = \left \{ \begin{aligned} \forall \text{ if k is even}\\ \exists \text{ if k is odd }\\ \end{aligned} \right.

{L \in \Pi_k} iff there are polynomials {p_1, \ldots , p_k} and a polynomial time computable function {F} such that

\displaystyle x \in L \Leftrightarrow \forall y_1.\exists y_2.\;\ldots Q_k' y_k. F(x,y_1,\ldots ,y_k)=1 \qquad

\displaystyle {\rm where} \; Q_k' = \left \{ \begin{aligned} \exists \text{ if k is even}\\ \forall \text{ if k is odd }\\ \end{aligned} \right.

For clarity, we omitted the conditions that each string {y_i} must be of polynomial length {(y_i\in \{ 0,1 \}^{p_i(|x|)})}.

One thing that is easy to see is that {\Pi_k = \mbox{co}\Sigma_k}. Also, note that, for all {i \le k-1}, {\Pi_i \subseteq \Sigma_k}, {\Sigma_i \subseteq \Sigma_k}, {\Pi_i \subseteq \Pi_k}, {\Sigma_i \subseteq \Pi_k}. This can be seen by noticing that the predicates {F} do not need to “pay attention to” all of their arguments, and so a statement involving {k} quantifiers can “simulate” a statement using less than {k} quantifiers.

Theorem 2 Suppose {\Pi_k = \Sigma_k}. Then {\Pi_{k+1} = \Sigma_{k+1} = \Sigma_k}.

Proof: For any language {L \in \Sigma_{k+1}}, we have that there exist polynomials {p_1, \ldots, p_{k+1}} and a polynomial time computable function F such that

\displaystyle x \in L \Leftrightarrow \exists y_1.\forall y_2.\;\ldots Q_{k+1} y_{k+1}. F(x,y_1,\ldots,y_{k+1})=1

where we did not explicitly stated the conditions {y_i\in \{ 0,1 \}^{p_i(|x|)}}. Let us look at the right hand side of the equation. What is following {\exists y_1} is a {\Pi_k} statement. Thus, there is a {L' \in \Pi_k} such that

\displaystyle x \in L \Leftrightarrow \exists y_1\in\{ 0,1 \}^{p_1(|x|)}.(x, y_1) \in L'

Under the assumption that {\Pi_k = \Sigma_k}, we have {L' \in \Sigma_k}, which means that there are polynomials {p'_1,\ldots,p'_k} and a polynomial time computable {F'} such that

\displaystyle (x, y_1) \in L' \Leftrightarrow \exists z_1.\forall z_2.\;\ldots Q_k z_k. F'((x,y_1),z_1,\ldots,z_k)=1

where we omitted the conditions {z_i \in \{ 0,1 \}^{p'_i(|x|)}}. So now we can show that

\displaystyle \begin{aligned} x \in L &\Leftrightarrow \exists y_1.(x, y_1) \in L' \\ &\Leftrightarrow \exists y_1.(\exists z_1.\forall z_2.\;\ldots Q_k z_k. F'((x,y_1),z_1,\ldots ,z_k)=1) \\ &\Leftrightarrow \exists(y_1,z_1).\forall z_2.\;\ldots .Q_k z_k. F''(x,(y_1,z_1),z_2,\ldots ,z_k)=1) \end{aligned}

And so {L \in \Sigma_k}.

Now notice that if {{\cal C}_1} and {{\cal C}_2} are two complexity classes, then {{\cal C}_1 = {\cal C}_2} implies {{\cal \mbox{co} C}_1 = {\cal \mbox{co} C}_2}. Thus, we have {\Pi_{k+1} = \mbox{co}\Sigma_{k+1} = \mbox{co}\Sigma_k = \Pi_k = \Sigma_k}. So we have {\Pi_{k+1} = \Sigma_{k+1} = \Sigma_k}. \Box

2. {{\bf BPP} \subseteq \Sigma_2}

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

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

\displaystyle \mathop{\mathbb P}_r (A(x,r) = \text{right answer}) \geq 1 - \tfrac{1}{3m},

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

Proof: Let {\hat{A}} be a BPP algorithm for {L}. Then for every {x},

\displaystyle \mathop{\mathbb P}_r (\hat{A}(x,r) = \text{wrong answer}) \leq \tfrac{1}{3},

and {\hat{A}} uses {\hat{m}(n)=n^{o(1)}} random bits where {n=|x|}.

Do {k(n)} repetitions of {\hat{A}} and accept if and only if at least {\dfrac{k(n)}{2}} executions of {\hat{A}} accept. Call the new algorithm {A}. Then {A} uses {k(n)\hat{m}(n)} random bits and

\displaystyle \mathop{\mathbb P}_r (A(x,r)=\text{wrong answer}) \leq 2^{-c k(n)}.

We can then find {k(n)} with {k(n)=\Theta(\log \hat{m}(n))} such that {\tfrac{1}{2^{c k(n)}} \leq \tfrac{1}{3 k(n) \hat{m(n)}}}. \Box

Theorem 4 {{\bf BPP} \subseteq \Sigma_2}.

Proof: Let {L} be in BPP and {A} as in the claim. Then we want to show that

\displaystyle x\in L \iff \exists y_1,\ldots,y_m \in \{ 0,1 \}^m \forall z \in \{ 0,1 \}^m \bigvee_{i=1}^m A(x,y_i \oplus z)=1

where {m} is the number of random bits used by {A} on input {x}.

Suppose {x\in L}. Then

\displaystyle \begin{aligned} & \mathop{\mathbb P}_{y_1,\ldots,y_m} (\exists z A(x,y_1\oplus z)=\cdots=A(x,y_m\oplus z)=0)\\ & \leq \sum_{z\in\{ 0,1 \}^m} \mathop{\mathbb P}_{y_1,\ldots,y_m} (A(x,y_1\oplus z)=\cdots=A(x,y_m\oplus z)=0)\\ & \leq 2^m \dfrac{1}{(3m)^m} \\ & < 1. \end{aligned}

So

\displaystyle \begin{aligned} & \mathop{\mathbb P}_{y_1,\ldots,y_m} \left(\forall z \bigvee_i A(x,y_i\oplus z)\right) \\ &= 1 - \mathop{\mathbb P}_{y_1,\ldots,y_m} (\exists z A(x,y_1\oplus z)=\cdots=A(x,y_m\oplus z)=0)\\ & > 0. \end{aligned}

So a sequence {(y_1, \ldots, y_m)} exists, such that {\forall z. \bigvee_i A(x,y_i \oplus z)=1}.

Conversely suppose {x \notin L}. Then fix a sequence {(y_1, \ldots, y_m)}. We have

\displaystyle \begin{aligned} \mathop{\mathbb P}_{z} \left(\bigvee_i A(x,y_i\oplus z)\right) & \leq \sum_{i} \mathop{\mathbb P}_{z} \left(A(x,y_i\oplus z)=1\right)\\ & \leq m \cdot \dfrac{1}{3m} \\ & = \dfrac{1}{3}. \end{aligned}

So

\displaystyle \begin{aligned} \mathop{\mathbb P}_{z} (A(x,y_1\oplus z)=\cdots=A(x,y_m\oplus z)=0) &= \mathop{\mathbb P}_{z} \left(\bigvee_i A(x,y_i\oplus z) = 0\right)\\ & \geq \dfrac{2}{3}\\ & > 0. \end{aligned}

So for all {y_1,\ldots,y_m \in \{ 0,1 \}^m} there is a {z} such that {\bigvee_i A(x,y_i\oplus z)=0}. \Box

1 thought on “CS254 Lecture 5 – The Polynomial Hierarchy”

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

Leave a comment