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)

$\endgroup$
0

1 Answer 1

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.

$\endgroup$
3
  • 1
    $\begingroup$ In the book (OP has a link to its draft) the error is in Example 5.6. $\endgroup$ Commented Oct 25, 2021 at 17:51
  • $\begingroup$ Thank you. Do you know a reference for completeness when assuming $\phi$ is in 3-DNF? $\endgroup$ Commented 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
    Commented Oct 26, 2021 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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