Complexity Class Π3P\Pi_3^{\mathsf{P}}

The decision problems of the form ∀y1∃y2∀y3 W(x,y1,y2,y3)\forall y_1 \exists y_2 \forall 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 coNP\mathsf{coNP} with a Σ2P\Sigma_2^{\mathsf{P}} oracle. These are the complements of the problems in Σ3P\Sigma_3^{\mathsf{P}}.

Reference

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