CS254 Lecture 5 – The Polynomial Hierarchy

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}$

$\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}$

$\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”

Henry Y on April 27, 2010 at 11:29 pm said:

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

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

CS254 Lecture 5 – The Polynomial Hierarchy

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

Leave a Reply

Share this:

Like this:

Related

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

Leave a Reply