# Is properly quantified 3SAT complete for PSPACE and all PH levels?

I know 3SAT is NP-complete and QSAT is PSPACE-complete. However, is it true that

$$\exists X_1 \forall X_2 \cdots Q_k X_k \colon \varphi(X_1, \ldots, X_k)$$

is complete for $$\Sigma_k$$, the existential side of level $$k$$ of the polynomial hierarchy if each clause in $$\varphi$$ has at most 3 literals (or some other constant size bound)? Similarly for

$$\forall X_1 \exists X_2 \cdots Q_k X_k \colon \varphi(X_1, \ldots, X_k)$$

in relation to $$\Pi_k$$, and the quantified version with unbounded alternation in relation to PSPACE, once again with each clause of $$\varphi$$ having at most 3 literals (or some other constant number)?

• Have you tried proving this yourself? Try mimicking the NP-hardness proof of 3SAT from SAT. Sep 6, 2019 at 21:54

Since the $$\Sigma_k$$ and $$\Pi_k$$ versions of QSAT can be reduced to equisatisfiable problems with 3 literals per clause using only a slight modification the method used to transform a SAT instance to 3SAT (i.e. putting all the new variables in the innermost existential group), those limited problems continue to be complete for their levels of the polynomial hierarchy.