1
$\begingroup$

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)?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Have you tried proving this yourself? Try mimicking the NP-hardness proof of 3SAT from SAT. $\endgroup$ – Yuval Filmus Sep 6 '19 at 21:54
3
$\begingroup$

QSAT with only 2 literals per clause was shown to be in P back in 1979.

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I thought there was a tricky corner case if the last quantifier is ∀: what if there's some large clause such that the existential player has to guess the exact mini-clause (in the reduction result) in which the universal makes the clause true? But the existential player can only be in that situation if the universal player can always falsify (one or more clauses of) the formula. So their inability to guess correctly reflects exactly the unsatisfiability of the formula, i.e. whenever the existential player has to guess, being unable to guess correctly is the desired state of affairs. $\endgroup$ – Jonas Kölker Oct 4 '19 at 17:30
  • $\begingroup$ Is there a standard paper to cite for this result? Probably it has worked over the corner cases more carefully than I have and it deserves credit. $\endgroup$ – Jonas Kölker Oct 4 '19 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.