[Solved]: Why does SAT not reduce to QBF?

Problem Detail: 

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?

Asked By : revisingcomplexity

Answered By : Tom Cornebize

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41403

 Ask a Question

 Download Related Notes/Documents