Suggest edit — polynomial hierarchy

Title

Name

Note

---
title: "polynomial hierarchy"
type: concept
related: [Conp, Non Polynomial Time, Polynomial Hierarchy]
source: https://www.jemoka.com/posts/kbhpolynomial_hierarchy/
confidence: high
status: active
---

\begin{equation} \text{PH} = \bigcup_{c \in \mathbb{N}} \Sigma_{c} = \bigcup_{c \in \mathbb{N}} \pi_{c} \end{equation}
&ldquo;a language is in the polynomial hierarchy if it can be described with a constant number of qualifiers&rdquo;
results and conjectures polynomial hierarchy conjecture &ldquo;the polynomial hierarchy is infinite&rdquo;&mdash;that is, each arrow to a harder language is strict.
$P \neq NP$, $NP \neq \pi_{2}$
PSPACE bounds the entire hierarchy $\text{PH} \subseteq \text{PSPACE}$
because for every $\exists$ you only have to keep one of it around.
polynomial hierarchy collapses $\text{P} = \text{NP} \implies \text{P} = \text{PH}$
&ldquo;the polynomial hierarchy collapses to $P$&rdquo; We study PH because it captures problems that are solvable efficiently if $\text{P} = \text{NP}$.
Recall&ndash;if $\text{P} = \text{NP}$, then $\text{P} = \text{NP} = \text{coNP}$. The fact that $\text{P} = \text{NP}$ lets you remove a quantifier, be it exists because $\text{P} = \text{NP}$ for all. Our claim is that:
$\text{P} = \text{NP}$, then $\text{ECLIQUE} \in P$. Recall ECLIQUE
Recall ECLIQUE can be written as:
\begin{align} &amp;\exists S \subseteq V, |S| = k, \text{ s.t. $S$ is k-clique} \\ &amp;\forall S&rsquo; \subseteq V, |S&rsquo;| = k+1, \text{ s.t. $S&rsquo;$ is not k-clique} \end{align}
to show the collapse, we define an &ldquo;inner language&rdquo; which captures the second half of this expression:
\begin{equation} \text{MQ} = \qty {\langle G,S,k \rangle, \forall S&rsquo; \subseteq V, |S&rsquo;| = k+1, S \text{ is clique, $S&rsquo;$ is not, $| S | = k$}} \end{equation}
MQ is the language with a poly-time checkable for-all, meaning its in coNP; using our assumption now, its also in P.
Therefore, we can write an equivalent ECLIQUE expression of the shape
\begin{equation} \text{ECLIQUE} = \qty {\langle G,k \rangle: \exists S \subseteq V, |S| = k, MQ\qty(G,S,k) = 1} \end{equation}
now this is in NP now, since we claim $\text{MQ} \in P$. Finally if $\text{NP} = \text{P}$, we see that $\text{ECLIQUE} \in P$.
less dramatic collapse Suppose we only have $\Sigma_{k} = \Pi_{k}$, then $\text{PH} = \Sigma_{k} = \Pi_{k}$ (because we can swap the last $k$ things and start eating up the left); sketch&mdash;
\begin{equation} \exists \forall \exists \forall \exists \forall \exists \end{equation}
suppose we can swap the last 2 (i.e. $\Sigma_{2} = \Pi_{2}$)
\begin{equation} \exists \forall \exists \forall \exists \qty(\exists \forall) \end{equation}
the two exists next to each other can be eaten up
\begin{equation} \exists \forall \exists \forall \exists \forall \end{equation}
and so on.
additional information $\Sigma$ and $L$ \begin{equation} L \in \Sigma_{2} \text{ if } \exists \text{ {polytime verifier $V$ s.t }} x \in L \Leftrightarrow \exists w_{1}\in \qty {0,1}^{\text{poly}\qty(|x|)} \forall w_{2} \in \qty {0,1}^{\text{poly}\qty(|x|)} V\qty(x, w_1, w_2) = 1 \end{equation}
\begin{equation} L \in \pi_{2} \text{ if } \exists \text{ {polytime verifier $V$ s.t }} x \in L \Leftrightarrow \forall w_{1}\in \qty {0,1}^{\text{poly}\qty(|x|)} \exists w_{2} \in \qty {0,1}^{\text{poly}\qty(|x|)} V\qty(x, w_1, w_2) = 1 \end{equation}
in general:
\begin{equation} L \in \Sigma_{k} \text{ if } \exists \text{ {polytime verifier $V$ s.t }} x \in L \Leftrightarrow \exists w_{1} \forall w_{2} &hellip; \underbrace{Q_{k}}_{\exists, \forall, \text{even or odd}} w_{k} V\qty(x, w_1, x_2, &hellip;, w_{k}) = 1 \end{equation}
$\pi_{k}$ is just like flipped, so we have $\forall$ first, and then $\exists$.
observations \begin{equation} \Sigma_{k} \subseteq \Sigma_{k+1} \end{equation}
\begin{equation} \pi_{k} \subseteq \pi_{k+1} \end{equation}
Also:
\begin{equation} \Sigma_{k} \subseteq \pi_{k+1} \end{equation}
\begin{equation} \pi_{k} \subseteq \Sigma_{k+1} \end{equation}