Computational Complexity HT25, Polynomial hierarchy

• $L \in \Sigma^p _ k$ iff there is a polynomial-time computable relation $R$ such that $x \in L$ iff $\exists y _ 1 \in \{0, 1\}^{p( \vert x \vert )} \forall y _ 2 \in \{0, 1\}^{p( \vert x \vert )} \cdots Q y _ k \in \{0, 1\}^{p( \vert x \vert )} \text{ s.t. } R(x, y _ 1, \ldots, y _ k)$.
  • (Here, there are $k$ quantifiers, alternating like $\exists \forall \exists \forall \cdots$. $\Sigma _ k^p$ always starts with $\exists$, but depending on whether $k$ is even or odd, the last quantifier $Q$ could be $\exists$ or $\forall$).
• $L \in \Pi^p _ k$ iff there is a polynomial-time computable relation $R$ such that $x \in L$ iff $\forall y _ 1 \in \{0, 1\}^{p( \vert x \vert )} \exists y _ 2 \in \{0, 1\}^{p( \vert x \vert )} \cdots Q y _ k \in \{0, 1\}^{p( \vert x \vert )} \text{ s.t. } R(x, y _ 1, \ldots, y _ k)$.
  • (Likewise, these quantifiers are alternating).
  • Alternatively, $L \in \Pi^p _ k$ iff $\overline L \in \Sigma^p _ i$.
• $\mathsf{PH} = \bigcup _ k \Sigma^p _ k = \bigcup _ k \Pi _ k^p$

\[\Sigma^p _ i\mathsf{SAT}= \\{\varphi : \exists u _ 1 \forall u _ 2 \cdots Q _ i u _ i \varphi(u _ 1, \ldots, u _ i) = 1\\}\]

where the quantifiers alternate and each $u$ is a vector of boolean variables, and $\Pi^p _ i\mathsf{SAT}$ has the quantifiers flipped. It is important that $\varphi$ is not assumed to be in 3CNF form; otherwise e.g. “$\Pi _ i^2\mathsf{SAT}$” would actually have a straightforward $\mathsf{NP}$ algorithm.

$\mathsf{SAT}$ is defined in terms of CNF formulas. It would not matter if it were defined in terms of any Boolean formula, as the Tseytin transformation gives a polynomial time algorithm for constructing equisatisfiable CNF formulas from any Boolean formula.

$\varphi$ is a tautology iff every clause contains a variable and its negation.

This is dual to the result that the satisfiability problem for DNF formulas can be solved in polynomial time.

@exam~ @example~

Since $\varphi$ is in 3CNF, the validity problem can be solved in polynomial time. This means that the final universal quantifiers don’t really count in the same way as the rest of the quantifiers.

@example~ @exam~

In the following let $x, y, z$ represent boolean vectors of variables.

Recall that

\[\Pi^p _ 2 \mathsf{SAT} = \lbrace \varphi(x, y) \mid \forall x \exists y \varphi(x, y) \text{ true} \rbrace\]

Let $L$ be an arbitrary language in $\Pi _ 2^p$. By the definition of $\Pi^p _ 2$, there is a polynomial-time relation $R$ such that $x \in L$ iff $\forall y \exists z R(x, y, z)$ where $y$ and $z$ are polynomially bounded in $ \vert x \vert $.

Consider the language $L’$ defined as follows: $\langle x, y \rangle \in L’$ iff $\exists z R(x, y, z)$. Clearly $L’ \in \mathsf{NP}$ by definition, since $R$ is polynomial-time computable.

By the $\mathsf{NP}$-completeness of $\mathsf{SAT}$, we can create in polynomial time a formula $\varphi(x, y, z)$ such that there is a satisfying assignment to $z$ iff $\langle x, y \rangle \in L’$.

By plugging in the input $x$ to an $L$ as assignment to $x$, we have $x \in L$ iff $\forall y \exists z \varphi(x, y, z)$ as desired.

@example~ @sheets~

\[\mathsf{MIN}\text{-}\mathsf{EQUIVALENT}\text{-}\mathsf{FORMULA} = \\{\langle \varphi, s \rangle \mid \exists \varphi' : |\varphi'| \le s \text{ s.t. } \varphi \equiv \varphi' \\}\]

$\mathsf{MIN}\text{-}\mathsf{EQUIVALENT}\text{-}\mathsf{FORMULA}$ is in $\Sigma^p _ 2$ since $\langle \varphi, s \rangle \in L$ iff $\exists \varphi’ \le s . \forall v \in \{0, 1\}^{ \vert \text{vars}(\varphi) \vert } . \varphi(v) = \varphi’(v)$.

Overall idea: Suffices to just show $\mathsf P^{\mathsf{NP} } \subseteq \Sigma^p _ 2$. Given $L \in \mathsf P^{\mathsf{NP} }$, we need to find some $R(x, y, z)$ such that $x \in L$ iff $\exists y \forall z R(x, y, z)$ is satisfiable. Use the existential quantifiers to encode queries that are answered positively, and the universal quantifiers to encode queries that are answered negatively.

Note that $\mathsf P^{\mathsf{NP} }$ is closed under complement, as given any language $L \in \mathsf P^{\mathsf{NP} }$, we may decide $\overline L$ by flipping the accept and reject states. Hence it suffices to show that $\mathsf P^{\mathsf{NP} }$ is contained in $\Sigma^p _ 2$, since if $L \in \mathsf P^{\mathsf{NP} }$, then $\overline L \in \mathsf P^{\mathsf{NP} }$ and so $\overline L \in \Sigma^p _ 2$ implies that $L \in \Pi _ 2^p$.

Let $L \in \mathsf P^{\mathsf{NP} }$, and let $M$ be a polynomial-time oracle Turing machine that decides $L$ with oracle access to $L’$, where $L’ \in \mathsf{NP}$. Define a polynomial-time relation $R$ such that

\[x \in L \iff \exists y \forall z R(x, y, z)\]

where $y, z$ are polynomially bounded in $ \vert x \vert $.

$R$ interprets the existential guesses $y$ as queries $q _ 1, \ldots, q _ k$ to $L’$ on $x$ that are answered positively, together with witnesses $w _ 1, \ldots, w _ k$ establishing that each $q _ i$ is a positive instance to $L’$.

$R$ interprets the universal guesses $z$ as queries $q _ 1’, \ldots, q’ _ {k’}$ to $L$ on $x$ that are answered negatively, together with universal guesses $w _ 1’, \ldots, w _ {k’}’$ to establish that each $q _ i’$ is a negative instance of $L’$.

To check that $R(x, y, z)$ holds, run $M$ on $x$ and check that the queries $q _ 1, \ldots, q _ k, q _ 1’, \ldots, q _ k’$ is a complete list of queries asked, assuming that any previous query $q _ j$ is answered positively and any previous query $q’ _ {j’}$ is answered negatively, and that the witnesses $w _ 1, \ldots, w _ k$ are correct witnesses for $q _ 1, \ldots, q _ k$ being in $L’$, and finally that $M$ does accept on $x$ when it makes the specified set of queries and receives the specified answers.

If $x \in L$, by making guesses corresponding to correct queries and answers, $R$ is satisfied. Likewise, if $R$ is satisfied, all guesses and answers are correct assuming that previously made guesses and answers are, and hence it must be the case that $M$ accepts on $x$.

@example~ @sheets~

Induct on $i$.

Base case: If $i = 1$, then we need to show $\Sigma^p _ 1 = \mathsf P$. But $\Sigma _ 1^p = \mathsf P$ by assumption.

Inductive step: Suppose $\Sigma^{p} _ {i} = \mathsf P$. By complementing both sides, we also see that $\Pi^p _ i = \mathsf P$. Let $L \in \Sigma^p _ {i+1}$. Then there is a relation $R \in \Pi _ i^p$ such that $x \in L$ iff $\exists y R(x, y)$. By the inductive step, we have that $R \in \mathsf P$ and thus $L \in \mathsf{NP}$. But then $L \in \mathsf P$ by assumption.

Define

\[\Delta^p _ 0 = \Sigma^p _ 0 = \Pi^p _ 0 := \mathsf P\]

Then for $i > 0$, define

• $\Delta^p _ {i+1} := \mathsf P^{\Sigma _ i^p}$
• $\Sigma^p _ {i+1} := \mathsf{NP}^{\Sigma _ i^p}$
• $\Pi^p _ {i+1} := \mathsf{coNP}^{\Sigma _ i^p}$

and set $\mathsf{PH} := \bigcup _ k \Sigma^p _ k = \bigcup _ k \Pi _ k^p$.

---

Therefore:

• $\Sigma^p _ 1 = \mathsf{NP}^{\mathsf P} = \mathsf{NP}$ is the set of languages decidable in nondeterministic polynomial time
• $\Pi^p _ 1 = \mathsf{coNP} = \mathsf{coNP}^{\mathsf P} = \mathsf{coNP}$ is the set of languages whose complement is decidable in nondeterministic polynomial time
• $\Sigma^p _ 2 = \mathsf{NP}^{\mathsf {NP} }$ is the set of languages decidable in nondeterministic polynomial time with access to a $\mathsf{SAT}$ oracle
• $\Pi^p _ 2 = \mathsf{coNP}^{\mathsf {NP} }$ is the set of languages whose complement is decidable in nondeterministic polynomial time with access to a $\mathsf{SAT}$ oracle