Tag Archives: uncited reduction

Quantified Boolean Formulas

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 {u1..un} of variables, a formula F that consists of a quantifier Qi for each ui that is either ∀ or ∃, and a boolean expression E bound to the quantifiers, is F true?

Example: ∀ u1 ∀ u2 ∃ u3  (u1 ∨ u2 ∨ u3).  This is true because for each value of u1 and u2, we can find a value for u3 (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.

Protected: Unification With Commutative Operators

This content is password protected. To view it please enter your password below:

Protected: Partially Ordered Knapsack

This content is password protected. To view it please enter your password below:

Protected: Minimum Weight Solution to Linear Equations

This content is password protected. To view it please enter your password below:

Protected: Integer Programming

This content is password protected. To view it please enter your password below:

Protected: Staff Scheduling

This content is password protected. To view it please enter your password below:

Protected: Three-Way Matching of Integers

This content is password protected. To view it please enter your password below:

Protected: Scheduling with Individual Deadlines

This content is password protected. To view it please enter your password below:

Protected: Conjunctive Boolean Query

This content is password protected. To view it please enter your password below:

Protected: Regular Expression Substitution

This content is password protected. To view it please enter your password below: