Is "3-QBF" defined similarly to 3-SAT is PSPACE-complete?

689 Views Asked by At

Define 3-QBF to be the language of all true-valued quantified 3-CNF boolean formulas.

When talking about NP-completeness, SAT is reducible in polynomial time to 3-SAT, which means that 3-SAT is also NP-complete.

Does this work also when talking about PSPACE-completeness? Is 3-QBF also PSPACE-complete?

1

There are 1 best solutions below

3
On

Yes, 3-QBF is PSPACE-complete. The same scheme that reduces a CNF clause with more than three literals to a 3-CNF clause works to produce equisatisfiable 3-QBF clauses and thus formulas. The bridge variables introduced to break up large clauses are existentially quantified and are placed in the innermost quantification group where they can be used to produce a satisfying assignment if one is possible in the original formula.