<p>No. Since universal quantifiers commute with conjunctions, it is easy to see that <span class="math-container">$\Sigma_2$</span>-SAT with <span class="math-container">$\psi$</span> CNF is in NP. If it's really written like this in the book, it's an error.</p>
<p>However, the problem is <span class="math-container">$\Sigma_2$</span>-complete for <span class="math-container">$\psi$</span> a 3-DNF.</p>

CC BY-SA 4.0
2021-10-25T17:51:51.147Z
In the book (OP has a link to its draft) the error is in Example 5.6.
Reijo Jaakkola
CC BY-SA 4.0
2021-10-26T09:04:58.083Z
Thank you. Do you know a reference for completeness when assuming $\phi$ is in 3-DNF?
Naama Shamash Hal
CC BY-SA 4.0
2021-10-26T11:19:01.000Z
@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.
Gamow
CC BY-SA 4.0
2021-10-25T15:31:50.420Z
2021-10-25T15:31:50.420Z
Emil Jeřábek
<p>It is known that the following problem is complete in <span class="math-container">$\Sigma_2^p$</span>:</p>
<p><span class="math-container">$\Sigma_{2}SAT$</span> : Given a quantified boolean formula <span class="math-container">$\theta = \exists x_1,...,x_l\forall y_1,...,y_m\psi$</span>, where <span class="math-container">$\psi$</span> is a boolean propositional formula over the variables <span class="math-container">$x_1,...,x_l,y_1,...,y_m$</span> , is <span class="math-container">$\theta$</span> valid?</p>
<p>Is it still complete when it is assumed that <span class="math-container">$\psi$</span> is in CNF?</p>
<p>It is mentioned in &quot;Computational Complexity: A Modern
Approach&quot; by Sanjeev Arora and Boaz Barak that it can be assumed, but no proof is given:
<a href="https://www.iith.ac.in/%7Esubruk/4510/phchap_arora.pdf" rel="noreferrer">https://www.iith.ac.in/~subruk/4510/phchap_arora.pdf</a>
(Example 5.9)</p>

<complexity-classes><polynomial-hierarchy>
Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$
Naama Shamash Hal
# Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$

(Asked by: username_0 on 2021-10-25)

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](https://www.iith.ac.in/%7Esubruk/4510/phchap_arora.pdf)
(Example 5.9)

**Tags:** complexity-classes, polynomial-hierarchy

---

## 1 answers

### Answer by username_1 on 2021-10-25. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_2**: In the book (OP has a link to its draft) the error is in Example 5.6.  
> **username_0**: Thank you. Do you know a reference for completeness when assuming $\phi$ is in 3-DNF?  
> **username_3**: @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.  

---

