Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that QBF, defined below, belongs to PSPACE.
Input: a quantified Boolean formula $$F = (Q_1x_1)(Q_2x_2) · · · (Q_nx_n)B(x_1, . . . , x_n)$$ where $B(x_1, . . . , x_n)$ is a Boolean expression in the variables $x_1, . . . , x_n$ and each $Q_i$ is a quantifier $\forall$ or $\exists$.
Question: is F true?

This is an exercise from chapter three of Complexity and cryptography by John Talbot and Dominic Welsh. Unfortunately I'm unsure how one must tackle such problems which are about PSPACE. I know the SAT problem is NP-COMPLETE and F is quite similar to it. (or is it not?) Please guide me trough the steps of its proof. I also know $NP \subset PSPACE$, so if we prove that this is NP it's PSPACE as well.

share|improve this question
Have you read en.wikipedia.org/wiki/PSPACE-complete#TQBF ? –  András Salamon Jun 26 '13 at 9:55
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.