Complexity Class Σ2P\Sigma_2^{\mathsf{P}}

The decision problems of the form ∃y1∀y2 W(x,y1,y2)\exists y_1 \forall y_2\, W(x, y_1, y_2), where y1,y2y_1, y_2 have size polynomial in ∣x∣|x| and WW is decidable in polynomial time. Equivalently, the problems solvable in NP\mathsf{NP} with an NP\mathsf{NP} oracle, Σ2P=NPNP\Sigma_2^{\mathsf{P}} = \mathsf{NP}^{\mathsf{NP}}. It forms the second level of the polynomial hierarchy together with Π2P\Pi_2^{\mathsf{P}}.

Reference

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

Referenced by