3
$\begingroup$

So, I remember the professor saying that SAT does not reduce to QBF (Quantifier Boolean Formula)

$QBF ::= prop|-QBF|(QBFoQBF)|\exists pQBF |\forall pQBF$

So, I guess this is not NP, since solving a QBF could grow exponentially.

However, $P \subseteq NP \subseteq PSPACE \subseteq PSPACE$-complete, so shouldn't I be able to reduce NP < PSPACE-complete, hence SAT < QBF?

The reduction would just use the same formula of PSAT in QBF.

Am I correct?

Improve this question
$\endgroup$
1
  • $\begingroup$ In short: A formula for SAT is a QBF with every variable existentially quantified. I'm not sure though what you mean by "solving a QBF could grow exponentially" $\endgroup$
    – Mike B.
    Commented Apr 15, 2015 at 10:45

1 Answer 1

Reset to default
7
$\begingroup$

First, be carefull, it might be that PSPACE ⊄ PSPACE-complete. If you suppose PSPACE ⊆ PSPACE-complete (thus PSPACE = PSPACE-complete since the other inclusion is true), then every problem of PSPACE is PSPACE-complete. Thus, all problems of PSPACE can be reduced to some easy problem of P (which is also in PSPACE). This is very unlikely (but not (yet) proved true or false).

Now, let us consider the reduction you propose.

If I understood well, you want to take a formula of SAT. The reduction would be to take the same formula for QBF (with, I suppose, an existential quantifier for each variable, otherwise it would not be a valid QBF formula).

This is indeed a valid reduction, and the SAT formula would be satisfiable if and only if the QBF formula was true.

By doing so, you reduce SAT to QBF. This shows that QBF is at least as hard as SAT. Since SAT is NP-complete, this shows that QBF is NP-hard.

The reduction in the other way (taking a QBF formula and making a SAT formula) is not known. This is why we do not know whether NP=PSPACE or not.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ You only show that QBF is NP-hard, not NP-complete. If QBF were NP-complete, then NP=PSPACE. $\endgroup$
    – Mike B.
    Commented Apr 15, 2015 at 11:10
  • $\begingroup$ Yep, I follow until the point you say it is NP-complete, which I think you mean NP-hard $\endgroup$
    – revisingcomplexity
    Commented Apr 15, 2015 at 12:18
  • 2
    $\begingroup$ Yes, sorry for that. I edited my answer. $\endgroup$
    – Tom Cornebize
    Commented Apr 15, 2015 at 17:14

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.