Notes - Computational Complexity HT25, Polynomial hierarchy
Flashcards
Suppose:
- $L \subseteq \{0, 1\}^\ast$
- $k \in \mathbb N$
@Define the polynomial hierarchy in this context, giving explicit definitions for $\Sigma^p _ k, \Pi^p _ k$ and $\mathsf{PH}$.
- $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 \forall 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 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 \exists 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$
@Define $\mathsf{MIN}\text{-}\mathsf{EQUIVALENT}\text{-}\mathsf{FORMULA}$ and state its location in the polynomial hierarchy.
\[\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)$.