Polynomial hierarchy

Remarks

The first level is $\Sigma_1^p = \mathrm{NP}$ and $\Pi_1^p = \text{co-NP}$. Example: the set of propositional formulas $\varphi(u, v)$ such that some assignment of $u$ makes $\varphi$ true for every assignment of $v$ is in $\Sigma_2^p$. Take $y_1 = u$, $y_2 = v$, and let $R$ be the set of triples $(\varphi, u, v)$ with $\varphi(u, v)$ true, which is in P.

Non-example: the number $k$ of quantifier blocks is fixed for each language in PH. The true quantified Boolean formula problem allows any number of alternations, and it is not known to be in PH. If it were in $\Sigma_k^p$, then PSPACE would equal $\Sigma_k^p$ and the hierarchy would collapse to level $k$.

With oracle machines the levels can also be written $\Sigma_{k+1}^p = \mathrm{NP}^{\Sigma_k^p}$, and one sets $\Delta_{k+1}^p = \mathrm{P}^{\Sigma_k^p}$. Then $\Sigma_k^p \cup \Pi_k^p \subseteq \Delta_{k+1}^p \subseteq \Sigma_{k+1}^p \cap \Pi_{k+1}^p$. If $\Sigma_k^p = \Pi_k^p$ for some $k$, then $\mathrm{PH} = \Sigma_k^p$.