Complexity Class Σ3P\Sigma_3^{\mathsf{P}}

The decision problems of the form ∃y1∀y2∃y3 W(x,y1,y2,y3)\exists y_1 \forall y_2 \exists y_3\, W(x, y_1, y_2, y_3), where the yiy_i have size polynomial in ∣x∣|x| and WW is decidable in polynomial time. Equivalently, the problems solvable in NP\mathsf{NP} with a Σ2P\Sigma_2^{\mathsf{P}} oracle.

Reference

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

Referenced by