# Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$

It is known that the following problem is complete in $$\Sigma_2^p$$:

$$\Sigma_{2}SAT$$ : Given a quantified boolean formula $$\theta = \exists x_1,...,x_l\forall y_1,...,y_m\psi$$, where $$\psi$$ is a boolean propositional formula over the variables $$x_1,...,x_l,y_1,...,y_m$$ , is $$\theta$$ valid?

Is it still complete when it is assumed that $$\psi$$ is in CNF?

It is mentioned in "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak that it can be assumed, but no proof is given: https://www.iith.ac.in/~subruk/4510/phchap_arora.pdf (Example 5.9)

• PSPACE=QSPACE: solving all qbfs is just as hard as solving one qbf, is mere Truth. +daniel GREs2380 Nov 9, 2021 at 14:29

No. Since universal quantifiers commute with conjunctions, it is easy to see that $$\Sigma_2$$-SAT with $$\psi$$ CNF is in NP. If it's really written like this in the book, it's an error.
However, the problem is $$\Sigma_2$$-complete for $$\psi$$ a 3-DNF.
• Thank you. Do you know a reference for completeness when assuming $\phi$ is in 3-DNF? Oct 26, 2021 at 9:04