# 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.

## Unification With Commutative Operators

The next problem is one of the “Private Communication” problems.  I’m going to try to take a stab at it myself.

The problem: Unification With Commutative Operators.  This is problem AN16 in the appendix.

The description: Given a set V of variables, a set C of constants, a set of n ordered pairs (ei, fi) (1 ≤ i ≤ n) representing “expressions”.  Each expression is defined recursively as either a variable from V, a constant from C, or (e+f) where e and f are expressions.  Can we create a way to assign each variable v in V a variable-free expression I(v) such that, if I(e) denotes the expression obtained by making all such replacements of variables in an expression e, that I(ei) ≡ I(fi) for all i?  We define e ≡ f as either:

• e = f  (the only possible way if e or f is a constant)
• If e = (a+b) and f = (c + d) then either (a ≡ c and b ≡ d) or (a ≡ d and b ≡ c)

Example:  Suppose C was {0,1}, and V was (x,y,z}.  We will have pairs ((x+y), (0+1)) and ((y + z), (0 + 0)).  Then substituting x with 1, and y and z with 0 makes the substituted pairs equivalent.

Reduction: I think this can be done with One-In-Three 3SAT.  The SAT instance defines variables x1..xk.  Each variable xi in the SAT instance will correspond to 2 variables in the set V in our unification instance: xi and ~xi.  Each clause in the SAT instance (l1, l2, l3) will turn into the expression (e,f) where the “e side” is (l1+l2+l3), where each li is the variable corresponding to the literal (i.e., either some xj or some ~xj).  The “f side” of all expressions is (1+0+0), which corresponds to exactly one of the literals being true.

We also need to add some extra expressions to make sure that we set each xi and ~xi to opposite signs.  So each variable xi in the SAT instance gets a pair whose “e side” is (xi + ~xi), and whose “f side” is 0+1.

I think that the unification instance we’ve constructed has a solution if and only if we can find a way to:

1. Set exactly one literal in each clause to true
2. Set exactly one of xi and ~xi to true, for all xi

..which is exactly when the original One-In-Three 3SAT instance was solvable.

I’ll admit to being a little worried about whether this is correct, because the comment in G&J talked about there being at most 7 constants or variables in an expression, and I did it with just 3.  Maybe it’s because I’m using One-In-Three 3SAT instead of regular 3SAT, or maybe I’m missing something.

Difficulty: 4 if I’m right.  I think starting from this version of 3SAT is a big hint.