2
$\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?

$\endgroup$
  • $\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. Apr 15 '15 at 10:45
6
$\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.

$\endgroup$
  • 1
    $\begingroup$ You only show that QBF is NP-hard, not NP-complete. If QBF were NP-complete, then NP=PSPACE. $\endgroup$ – Mike B. Apr 15 '15 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 Apr 15 '15 at 12:18
  • 2
    $\begingroup$ Yes, sorry for that. I edited my answer. $\endgroup$ – Tom Cornebize Apr 15 '15 at 17:14

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.