Monthly Archives: February 2019

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.

Integer Expression Membership

The last problem in this section!

The problem: Integer Expression Membership.  This is problem AN18 in the appendix.

The description: Given an integer expression e over the expressions ∪ and +, which work on sets of integers.   The ∪ operation unions two sets of integers together, and the + operation takes two sets of integers and creates the set of sums of elements from each of the sets.  Given an integer K, is K in the set of integers represented by e?

Example: Suppose A = {1,2,3}, B = {4,5,6}, C = {1,3,5}.

Then the expression (A∪C) would be {1,2,3,5} and the set (A∪C) + B would be {2,4,6,3,5,7,6,8,10}.  So if we were given that expression and a K of 8, a solver for the problem would say “yes”, but if given a K of 9, the solver for the problem would say “no”.

Reduction: Stockmeyer and Meyer show this in their Theorem 5.1.  They reduce from Subset Sum (they call it Knapsack, but their version of Knapsack doesn’t have weights, so it’s out Subset Sum problem).  So from a Subset sum instance (a set A = {a1, …, an} and a target B), we build an expression.  The expression is (a1 ∪ 0) + (a2 ∪ 0) + …  + (an ∪ 0).  Then we set K=B.

Notice that the set of integers generated by this expresion is the set of all sums of all subsets of A.  Asking is B is a member is just asking if there is a way to make the above expression (for each element ai, either taking it or taking 0) that adds up to exactly B.  This is exactly the Subset Sum problem.

Difficulty: 4.  The reduction itself is easy.  It might be hard to explain the problem itself though.

Unification for Finitely Presented Algebras

The example below (using Boolean Algebra) is the kind of description of an “Algebra” that I wish I had when I learned this stuff in school- we did a lot of stuff with modular arithmetic, that I think was a lot harder.

The problem: Unification for Finitely Presented Algebras.  This is problem AN17 in the appendix.

The description: Given a description of an algebra as a set G of generator symbols, a set O of operator symbols (of possibly varying dimensions), and a Γ of “defining relations” over G and O.  We’re also given two expressions x and y over G and O, and a set of variables V.   Can we find “interpretations” for x and y, called I(x) and I(y) such that I(x) and I(y) are formed by replacements of variables such that I(x) and I(y) represent the same element of the algebra?

Example: The paper by Kozen that has the reduction gives a pretty good example of an algebra: Suppose G was {0,1}, O was {∧, ∨, ¬}, and Γ was {0∧0 ≡ 0, 0 ∧ 1 ≡ 0, 1 ∧ 0 ≡ 0, 1 ∧ 1 ≡ 1, 0 ∨ 0 ≡ 0, 0 ∨ 1 ≡, 1 ∨ 0 ≡ 1, 1 v 1 ≡ 1, ¬0 ≡ 1, ¬1 ≡}.  This is the normal Boolean Algebra we see everywhere.

Now we can ask questions like: If x = a ∨ b ∨ c and y = 0 ∨ 1 ∨ d, can we find a unification of the variables that makes the equations the same?  The answer is yes, with the replacements {a/0, b/1, d/c}.

I think the  “represent the same element” part of the problem statement means that we can also take advantage of unification rules, so we can ask questions like does ~x ∨ y ∨ ~z unify to 1?

Reduction: Kozen’s paper makes the point that if we use the Boolean Algebra that we used in the example, then the Satisfiability problem can be represented in Boolean Algebra using the rules above, and the question “Is this formula satisfiable” can be recast as “Does this formula unify to true?”

He doesn’t provide the proof, though, so I hope I’m representing him correctly.

Difficulty: 4.  Once you see how the Boolean Algebra relates, it’s pretty easy.

Protected: Unification With Commutative Operators

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