Complexity Class $\Pi_2^{\mathsf{P}}$

The decision problems of the form $\forall y_1 \exists y_2\, W(x, y_1, y_2)$ , where $y_1, y_2$ have size polynomial in $|x|$ and $W$ is decidable in polynomial time. Equivalently, the problems solvable in $\mathsf{coNP}$ with an $\mathsf{NP}$ oracle. These are the complements of the problems in $\Sigma_2^{\mathsf{P}}$ .

Reference

Stockmeyer, L.J. (1976). The Polynomial-Time Hierarchy. Theoretical Computer Science, 3(1), pp. 1–22.

Referenced by

Complexity Class $\mathsf{D}_2^{\mathsf{P}}$
Complexity Class $\Sigma_2^{\mathsf{P}}$

Complexity Class Π2P\Pi_2^{\mathsf{P}}

Reference

Referenced by

Complexity Class $\Pi_2^{\mathsf{P}}$