[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhpolynomial_hierarchy.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "polynomial hierarchy" source: https://www.jemoka.com/posts/kbhpolynomial_hierarchy/ --- \begin{equation} \text{PH} = \bigcup_{c \in \mathbb{N}} \Sigma_{c} = \bigcup_{c \in \mathbb{N}} \pi_{c} \end{equation} “a language is in the polynomial hierarchy if it can be described with a constant number of qualifiers” results and conjectures polynomial hierarchy conjecture “the polynomial hierarchy is infinite”—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}\) “the polynomial hierarchy collapses to \(P\)” We study PH because it captures problems that are solvable efficiently if \(\text{P} = \text{NP}\). Recall–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} &\exists S \subseteq V, |S| = k, \text{ s.t. $S$ is k-clique} \\ &\forall S’ \subseteq V, |S’| = k+1, \text{ s.t. $S’$ is not k-clique} \end{align} to show the collapse, we define an “inner language” which captures the second half of this expression: \begin{equation} \text{MQ} = \qty {\langle G,S,k \rangle, \forall S’ \subseteq V, |S’| = k+1, S \text{ is clique, $S’$ 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— \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} … \underbrace{Q_{k}}_{\exists, \forall, \text{even or odd}} w_{k} V\qty(x, w_1, x_2, …, 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}