8
$\begingroup$

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)

Improve this question
$\endgroup$
1
  • $\begingroup$ PSPACE=QSPACE: solving all qbfs is just as hard as solving one qbf, is mere Truth. +daniel GREs2380 $\endgroup$
    – daniel pehoushek
    Nov 9, 2021 at 14:29

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ In the book (OP has a link to its draft) the error is in Example 5.6. $\endgroup$
    – Reijo Jaakkola
    Oct 25, 2021 at 17:51
  • $\begingroup$ Thank you. Do you know a reference for completeness when assuming $\phi$ is in 3-DNF? $\endgroup$
    – Naama Shamash Hal
    Oct 26, 2021 at 9:04
  • 5
    $\begingroup$ @Naama Shamash Hal: Celia Wrathall ("Complete sets and the polynomial hierarchy", Theoret. Comp. Sci., 3:23-33, 1976) proves completness for DNF-formulas in Corollary 6 on page 32; the step from DNF to 3-DNF is straightforward. $\endgroup$
    – Gamow
    Oct 26, 2021 at 11:19

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.