A complexity class which is likely to be properly contained in \(\textbf{EXP}\) but which still contains many apparently infeasible problems which arise in computational practice is \(\textbf{PSPACE}\). A prototypical example of a problem in \(\textbf{PSPACE}\) can be formulated using the notion of a quantified boolean formula [QBF] – i.e. a statement of the form \(Q_1 x_i \ldots Q_n x_n\psi\) where \(Q_i = \exists\) or \(\forall\) and \(\psi\) is a formula of propositional logic containing the propositional variables \(x_1,\ldots,x_n\) which are treated as bound by these quantifiers. A QBF-formula is said to be true if when \(Q_i x_i\) is interpreted as an existential or universal quantifier over the truth value which is assigned to \(x_i\), \(\psi\) is true with respect to all of the valuations determined by the relevant quantifier prefix – e.g. \(\forall x_1 \exists x_2 (x_1 \vee x_2)\) is a true quantified boolean formula, while \(\forall x_1 \exists x_2 \forall x_3 ((x_1 \vee x_2) \wedge x_3)\) is not. We may now define the problem