# Tag Archives: Difficulty 9

## Minimum Disjunctive Normal Form

LO7 is Satisfiability of Boolean Expressions, which is what we now call Cook’s Theorem. It’s related to the “regular” (clause-based) Satisfiability we’ve done all along because it’s possible to turn any Boolean expression into CNF form.

LO8 is DNF Non-Tautology.

The next problem’s paper was written in 1965, so before NP-Completeness was a concept.  As a result, the paper doesn’t line up exactly with what we want to do, and I think I’m misunderstanding something.

The problem: Minimum Disjunctive Normal Form.  This is problem LO7 in the appendix.)

The description: Given a set u1 through un of variables, a set A of n-tuples containing T or F symbols (possible truth assignments of the variables), and an integer K, can we create a DNF form expression E that is true for the variable set exactly for the truth assignments in A (everything in A and nothing more) using K clauses or less?

Example: Suppose we had 3 variables, and A was {(T,T,F), (T,F,F)}.

Then the DNF expression (u1 ∧ u2 ∧ ~u3) ∨ (u1 ∧~u2 ∧ ~u3) will be true only on the truth assignments listed in A.

We can get away with less than “one clause for each element of A” though.  For example, if A = {(T,T,T), (T,T,F), (T,F,T), (F,T,T), (T,F,F), (F,T,F)}  then we can just use u1 ∨ u2 to cover exactly those truth assignments.

Reduction: The paper by Gimpel was written in 1965 (before Cook’s 1971 paper), so wasn’t conceived of as an NP-Completeness reduction.  But it does show how to translate from Set Covering.

The basic idea is that we will represent a covering instance as a 0/1 table A.  We start with an m by n table, with variables representing the rows and sets representing the columns (aij = 1 means that variable i is in set j)

We’re now going to build some boolean expressions over m+n variables:

pi = u1 ∧ u2 ∧ … ∧ ~ui ∧ … ∧ um+n

(All of the positive variables and-ed together, except the negation of ui)

f1 = p1 ∨ p1 ∨ … pn

Fi = {j | aij = 0}  (The set of all variables not in set i)

Pi = un+i ∧ uj (the conjunct of all uj where j ∈ Fi)

f2 = P1 ∨ … Pn

Then he proves that f1 and f2 form a pair of functions for which A is the prime implicant table of those functions.  By which he means that aij = 1 if and only if pj ∈ Pi.

Then we build a table B that represents the prime implicant table of a related function.  If we remove the last r rows and 2r columns from B (I think this is related to K somehow), we get a table that is equivalent to our A.

Difficulty: 9.  I’m pretty sure I’m missing something here.  I don’t see how these tables relate.  I don’t see how you can take f1 and f2 and make a single DNF formula out of them.  I don’t see where K shows up- I guess it’s a limit on n?  But how does it relate to the covering matrix?

## Square Tiling

The reference in G&J is to an “unpublished result” (by Garey and Johnson themselves, with Papadimitriou).  I think the solution I found is not the one they are referring to.

The problem: Square Tiling.  This is problem GP13 in the appendix.

The description: Given a set C of colors, and a set T of tiles, where each of the 4 sides of the tile are colors from C (listed as a 4-tuple of (top, right, bottom, left) colors), and an integer N.  Can we tile an NxN square of tiles using tiles from C?  We can use a tile more than once, the tiles can’t be rotated, and adjacent edges need to match colors.

Example: Here are some example tiles I drew: We can tile these into a 3×3 grid like this: Reduction: As I said above, the reference in G&J is to an “unpublished result” by Garey, Johnson, and Papadimitriou.  I did manage to find a “generic reduction” using Turing Machines in the Lewis and Papadimitriou Theory book.

The reduction is from the “N2” language in the book, which (I think) is “Can a Turing Machine M halt in t steps or less with its head on the tape in configration uσv, where u and v are strings in Σ*, and σ is the location of the head (and a symbol in the alphabet)?

The idea is that we’ll build a set of tiles whose colors are based on the number of steps the computation has done so far.  The colors are actually tuples.  So, we have several kinds of tiles:

• For each a in Σ*, and each k from 1 to t, a tile with color (a, k+1) on the top, and (a,k) on the bottom.  This simulates a move that stays in the same state and writes the same symbol.
• For each pair a,b in Σ*, and each state p,q in M (p can include the halt state, q can’t), a tile with the color (p,b,k+1) on the top and (q,a,k) on the bottom.  This simulates going from state p to state q and replacing an a with a b.
• We can transition from one of the above types of tiles to another using a sideways move.  (If the head moves left or right, we move to a tile to the left or right)
• There are special tiles for the start row and for when the machine halts.

We set our N (the size of the tiling grid we’re making) to t+2.  What we’ve built is a system that:

• Has to have the tiles corresponding to one of the start states on the bottom row
• Has in row i a tile corresponding to a configuration of the machine after i steps.  (A path of tiles from the bottom to row i show the computation needed to get to that state)
• Has at the top row a tile corresponding to a configuration after t+1 steps.  If there is a legal tiling, one of those tiles must contain the halt state.

..which they claim is the same as the N2 langauge.

The suggested reduction in the appendix is from Hamiltonian Path, and I spent some time thinking about how to make that work, but couldn’t do it.  Do you make tiles correspond to vertices? Do you make colors correspond to vertices?  How do you account for the fact that you can go in two dimensions?  How do you account for the fact that you don’t know the order in which you visit the tiles?  I think it might be similar to this way of thinking about configurations.

Difficulty: 9 because it’s such a non-standard way of doing things.  I bet the Hamiltonian Path reduction is a lot easier.