The next section in the appendix is the “Games and Puzzles” section. But many of the reductions refer to this problem, so we’ll do this first.

**The problem: **Quantified Boolean Formulas (QBF). This is problem LO11 in the appendix.

**The description: **Given a set U {u_{1}..u_{n}} of variables, a formula F that consists of a quantifier Q_{i} for each u_{i} that is either ∀ or ∃, and a boolean expression E bound to the quantifiers, is F true?

**Example: **∀ u_{1} ∀ u_{2} ∃ u_{3} (u_{1} ∨ u_{2} ∨ u_{3}). This is true because for each value of u_{1} and u_{2}, we can find a value for u_{3} (namely “true”) that makes the expression true.

**Reduction:** G&J send you to the paper by Stockmeyer and Meyer that we did last week, and calls it a “generic transformation”, which means it builds a Turing Machine, similar to how Cook’s Theorem does.

But I think you can do a regular reduction from 3SAT: Given a SAT instance, we add a ∃ quantifier for each variable and then use the SAT formula as our E expression in this problem. Then we’re just asking whether there exist values for each variable that make the formula true.

**Difficulty: **3, assuming I’m not missing something. I always worry when I find a “short cut” like this.