Tag Archives: 3-sat

Pruned Trie Space Minimization

This problem is hard to explain, partially because the definition given by G&J doesn’t really map to the structure they are talking about easily.

The problem: Pruned Trie Space Minimization.  This is problem SR3 in the appendix.

The description in G&J: Given a finite set S, a collection F of functions mapping elements of S to positive integers, and a positive integer K.  Can we find a sequence of m distinct functions from F <f1 .. fm> such that:

  • For each pair of elements a and b in S, there is some function fi in the sequence where fi(a) ≠ fi(b)
  • For each i from 1 to m, define N(i) to be the number of distinct tuples X= (x1..xi) where more than one a in S has the tuple (f1(a), …, fi(a)) = X, the sum of all of the N(i) values is at most K?

A better description: G&J’s definition removes all knowledge of the “tries” from the problem.  The Comer and Sethi paper that is referred to in the appendix I think does a better job.

First, a trie is a tree that separates a sequence of strings by letters. The idea is that each string has a unique path through the tree.  Here is the tree used in the paper:


This trie shows the path for the set of strings: {back, bane, bank, bare, barn, band, bang, barb, bark, been} by building the tree by considering letters in the string from left to right.  By using different orders of considering letters, we will get differently shaped tries, with different numbers of internal nodes.

A pruned trie recognizes that long paths of nodes with 1 child doesn’t actually need to be represented.  For example, once you go down the “b-e” side, the only place you can end up is at “been”.  So the trie is pruned by removing all such chains (we would consider the “e” node a leaf).

What we are interested in doing is finding an ordering on the letters in the string (or, more generally, the “attributes” of an element we are trying to distinguish) in order to minimize the number of nonleaf nodes in the pruned trie.

The actual question we want to solve is: Given a set of strings S and an integer K, can we construct a trie that differentiates the S strings with K or less internal nodes?

I think the way this maps to the G&J definition is:

S is the set of strings.  F is the set of attributes that map strings to an order of choosing attributes.  The sequence of functions <f1, …, fn> are the orders in which we choose attributes.  So f1(a) is the first node in the trie that we go to on the string a, f2(a) is the second node we go to and so on.  The fi(a) ≠ fi(b) requirement says that we need to eventually differentiate each string from each other, and the N(i) number is counting the number of internal nodes at each height of the tree:

Example: For the picture shown above, we get the following pruned trie (also from the paper):


This trie has 5 internal nodes.

Reduction: G&J say that the reduction goes from 3DM, but in the paper it goes from 3SAT. So we’ll start with a formula in 3CNF form with n variables and m clauses.  The strings we’ll build will have 3n+3m attributes (you can think of this as strings of length 3n+3m).    The first 2n attributes will correspond to literals (one attribute for the positive setting of a variable, one attribute for the negative setting).  The next 3m attributes will correspond to clauses (3 attributes for the 3 possible positions a variable can appear in a clause), and the last 3 attributes correspond to literals (to combine the positive and negative setting of that variable’s literals).

We will have one string for each literal (a 1 in the attribute matching that literal’s positive or negative setting, a 1 in the attributes matching that literal’s position in clauses, and a 1 in the attribute matching that variable, 0’s everywhere else).  We will have one string for each clause (a 1 in the three positions in each clause, 0’s everywhere else).  Then we will have a sequence of “hard to distinguish” strings made of decreasing numbers of 2’s (with 0’s everywhere else).

Here’s the example construction from the paper (blank spaces are zero’s).  It’s a little confusing because they chose n=m=3, but you can see where the various pieces are:pruned-trie-space-minimization3


If the formula is satisfiable, then the ordering of attributes where we put all of the literals that form the satisfying arrangement first, then all of the clauses, then the W attributes (for the variables) distinguishes the strings in L with 2n+m internal nodes.

In fact, all tries must have at least K internal nodes to distinguish the strings in L- that can be seen from the table, since we have K strings made up of decreasing numbers of 2’s.  We also have to distinguish the strings in order (the strings with the most 2’s first, then the ones with less 2’s, all the way down to the last one with just one 2).  We need to choose one attribute for each literal (positive or negative).  Suppose we choose an attribute Ui (or its negation).  That node in the trie has 3 children:

  • A 2, which distinguishes the string in L.
  • A 1, which distinguishes the string corresponding to that literal in J.
  • A 0, for everything else.

What this means is that we have “distinguished off” the literal string (in J) from the rest (on a 1), which means that the 1 it has in the clause position will not interfere with the 1 in that position of the clause string (in K).  So each clause string will be able to be distinguished by the clause position that satisfies the string.

So, if we have a trie with “only” K internal nodes, the attributes must line up to allow us to have a setting of a variable to satisfy each clause.

Difficulty: 8, with the Comer and Sethi trie definition.  If you are going straight from G&J’s definitions, it’s at least a 9.

Protected: Polynomial Non-Divisibility

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


The other major reduction my student, Dan Thornton, was working on was a reduction for the old NES Pokemon game.

This is Dan’s last reduction for his independent study class.  He’s going to be applying to grad schools this year- if you’re running a grad program, you should accept him!

(Over to Dan)

The Problem:
Here we prove that a generalized version of the classic Pokemon Red/Blue video game is NP-complete.  Generalized Pokemon(hereafter referred to as GP) asks the following question: Given a party of Pokemon and a map of trainers, can you get from the start position to the end position without having all of your Pokemon defeated in battle and continue your journey of catching them all?

This is based off of a paper by Aloupis, Demaine, Guo, and Viglietta on classical Nintendo games.

The goal of any Pokemon game is progress through the world collecting all Pokemon to become the very best Pokemon trainer there ever was. For more background see this link. We will focus on a subproblem where there is a path filled with enemy trainers from a start point to some end point. Solving GP and determining if we can get to the finish from the start turns out to be NP-complete.

In our construction of GP, there are two types of enemy trainers we will encounter, Hard trainers which we will always lose against, and Easy trainers which we will always win against. The details of this construction will be described below.

The description:
Here we reduce GP from 3 SAT by building certain constructs or gadgets in GP that can be used to model clauses, variables, variable assignment, and satisfiability. Then inductively using these component pieces we may build an instance of GP that is logically equivalent to one from 3SAT. Below is the framework that we will map components of GP on to.


In the above figure all solid lines are single use paths, all dashed lines have no traversal limit.

The idea is that our trainer starts at the Start location and proceeds to a variable gadget, they then have an exclusive choice between two paths. One path reflects the assignment of true, the other of false. This choice will take us to a series of paths that will let us proceed to each clause the variable assignment satisfies and unlock it. Then we move on to the next variable. Eventually after proceeding through all of the variable clauses, we arrive at the Check in phase. Here we try to pass through all of the clauses, only the clauses we previously satisfied with the correct variable assignment may be passed through. Now if all clauses are satisfied, then we are able to pass through every one and arrive at the Finish state.

As an example in the above figure the colored edges give use a path that will satisfy all the clauses and pass to the Finish. The red edges show us assigning the value of true to x then proceeding to the first and second clause which are satisfied by this assignment of x. The blue edges show an assignment for y and the green one for z. It is important to note that we are unable to move backwards except on dashed edges, this prevents us from going back and attempting to correct our variable assignment.

To show equivalence we break any 3SAT instance up into to following: F = \wedge_{i=1}^{n} C_{i}. Here each clause is of the form:
C_{i} = x_{i1} \vee ... \vee x_{ik_i} where
k_{i} < 4
and each x_{ik_i} is a literal of the form \neg z_{l} \ or \ z_{l}.


The construction of the GP instance is built out of several component pieces,  each described below.

Trainer Construction

Our trainer has a single Pokemon, a Ghastly that knows only a single move– Self-Destruct, a move that when used causes the user to faint but deals massive damage to a single enemy Pokemon. If it is ever our trainer’s turn during a battle we are forced to use a move.

By the above, if we ever use a move, we lose due to us only having a single suicidal move and a single Pokemon. When we lose we are unable to move and will be unable to get to the Finish.

Hard trainers have two Snorelaxs, both of which are slower than our Ghastly, so when we go into battle against them we are forced to use self-destruct and lose. Even if we cause a single of the opponent’s Snorelax to faint we still lose the battle as they have another.

Easy trainers all have a single Electrode that only knows self-destruct and has more speed than our Ghastly, so they will always go first and destroy themselves. Now normally self destruct would also deal massive damage to our Ghastly but, because Ghastly is a ghost type Pokemon, and self-destruct is a normal type move, it will not effect our Ghastly. Thus the opposing trainer will run out of Pokemon before us, and we win.

So, we have a situation where we may encounter any number of weak trainers and win, but a battle with a strong trainer guarantees a loss.

Field of Vision


Enemy trainers have a “field of vision” of some fixed length. In the above Figure, Player A’s field of vision is given by all blue squares. Once a player enters a trainer’s field of view they will be unable to move, the enemy trainer who can see them will approach and the trainer will be forced to battle. Other enemy trainers can block a trainers field of view, for example the striped blue box above is no longer in trainer A’s field of view due to trainer B.

Alternatively we may choose to force an enemy trainer to battle our trainer if we stand in any of the orange squares.

Finally once an enemy trainer has been defeated they will remain on the square they were defeated on indefinitely, so if we challenged and beat trainer A with our trainer standing on any of the orange squares, then trainer A would stay on the exact square he is on even if our trainer moved into his field of vision (any of the solid blue squares).

To distinguish the two types of trainers hard trainers will have a blue field of vision, where as easy trainers will have a red one.

Variable Construction
Variable assignment may be modeled using the construction in Figure 3. Here the player enters through a. The player may either choose to move to battle the enemy trainer while standing on square x or y. If our trainer battles the enemy trainer on square x then the enemy trainer will block off the c exit, and once defeated will stay there indefinitely. Alternatively if our trainer battles on square y then the defeated enemy trainer will remain where he is indefinitely and we must exit through c. So this construction therefore presents the player with an exclusive choice between two possible paths b or c.

Single Use path
In order to prevent a player from re-tracing his or her steps to access previous paths we may use the construction below. Here if we assume a player enters from a and will exit through b.

Notice that to pass from a to b our player must pass through both squares marked x and y. Notice that once we pass through y trainer C will have moved forwards to battle our trainer at y. This now means that trainer B has line of sight to x. Now because we must go through x square to get from a to b or b to a any passage through this gadget will be impossible.

Also notice that if we enter from b then we must pass through y before x and so by the same argument as above this is impossible.

Trainer A simply serves as a barrier from letting us battle trainer C from an adjacent square.

So this gadget is a single use unidirectional path.


Below we illustrate a 3SAT clause, each of the weak trainers is a literal.
If the player at any time enters through any of the three literal paths from above, then they may battle a weak trainer. If a player battles any of the weak trainers then later on when the clause gadget is entered through check in then the weak trainer the player already battled will not approach the player, and will instead continue to block hard trainer B’s field of vision so that we may pass through to check out. Hard trainer A is there just to prevent re-entering the literal clauses after entering this gadget through check in.


The crossover gadget shown below is present to deal with the issue of planarity, as there is no device in the original Pokemon games for passing “over” other portions. Then if we view the paths between gadgets as edges of a graph similar to our framework in the first figure, then without this gadget we are restricted to building planar graphs.

This gadget lets two paths cross without letting a player switch the path they are on. So if you enter from x a player is forced to leave through x' and similarly for y and y'. Each path is single use, but using the x‘s path, has no effect on our use of the y‘s path and vice versa.  As a result we may assume we can build a single use path between any two points.


Here we reduce from an instance of 3SAT. We are given a formula F with the form defined in section 4. Now we build F into an instance of GP using the reduction framework in Figure 1 as well as our components. We also impose the restriction that in every variable gadget path b corresponds to assigning a literal the value True and c corresponds to False.

True_{3SAT} \Rightarrow True_{GP}
If we have a variable assignment \phi_{F} that satisfies F then by definition there is a literal z_{j} in every clause C_{i} such that z_{j} satisfies C_{i}. Then in our constructed instance of GP we must be able to visit the literal section of every clause gadget at least once prior to arriving at the check-in phase. So it follows that we are able to battle at least 1 of the easy trainers in each clause gadget before check-in. Therefore it must be possible for us to reach the finish.

True_{GP} \Rightarrow True_{GP} True_{3SAT}
If it is possible for our trainer to get from start to finish, then again by the framework in Figure 1 we must be able to battle an easy trainer in each of our clause gadgets. To reach these clause gadgets the trainer had to make an exclusive decision in each variable gadget. This choice corresponds to a literal assignment. So the path our trainer takes through the variable gadgets, and then through the clause gadgets to the finish gives us an assignment of literals such that every clause is satisfied. Obviously this corresponds to an assignment that satisfies F.

(Back to me)

Difficulty: 9.  This isn’t that hard to understand, but there are lots of details that are needed- having to position the trainers in exactly the right position for it all to work.

Protected: Maximum Fixed-Length Disjoint Paths

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

Protected: Maximum Length-Bounded Disjoint Paths

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

Protected: DNF Non-Tautology

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

Protected: Path Constrained Network Flow

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

Monotone 3-Satisfiability

I told Daniel when he gave me his Monotone Satisfiability reduction that the actual problem mentioned in G&J was Monotone 3-Satisfiability.  So he went off and did that reduction too.
The Problem:
Monotone 3 SAT. This is a more restrictive case of Monotone SAT

The Description:
Given an formula of clauses F' = \wedge_{i=1}^{n} C'_{i} where each clause in F' contains all negated or non-negated variables, and each clause C_{i} contains at most 3 variables. Does there exist an assignment of the variables so that F' is satisfied?


\\ F_{1} = (x_{1} \vee x_{3}) \wedge \\ (\neg x_{2} \vee \neg x_{3} \vee \neg x_{4}) \wedge  \\ (x_{3} \vee x_{2} \vee x_{4}) \wedge \\ ( \neg x_{3} \vee \neg x_{5} \vee \neg x_{1})
the following assignment satisfies F'_{1}:
\\  x_{1} \mapsto True\\ x_{2} \mapsto False\\ x_{3} \mapsto True\\ x_{4} \mapsto True\\ x_{5} \mapsto False
\\ F_{2} = (\neg x_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge \\ (x_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge\\ (\neg x_{1} \vee x_{2} \vee \neg x_{3})\wedge \\ (\neg x_{1} \vee \neg x_{2} \vee x_{3})\wedge\\ (x_{1} \vee x_{2} \vee \neg x_{3})\wedge\\ (\neg x_{1} \vee x_{2} \vee x_{3})\wedge\\ (x_{1} \vee \neg x_{2} \vee x_{3})\wedge\\ (x_{1} \vee x_{2} \vee x_{3})
And the following is F_{2}' in Monotone  3SAT form:
\\ F_{2}' = (\neg x_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge \\ (\neg y_{1} \vee \neg x_{2} \vee \neg x_{3}) \wedge\\ (\neg x_{1} \vee \neg y_{2} \vee \neg x_{3})\wedge \\ (\neg x_{1} \vee \neg x_{2} \vee \neg y_{3})\wedge \\ (x_{1} \vee x_{2} \vee y_{3})\wedge\\ (y_{1} \vee x_{2} \vee x_{3})\wedge\\ (x_{1} \vee y_{2} \vee x_{3})\wedge\\ (x_{1} \vee x_{2} \vee x_{3}) \wedge \\ (y_{1} \vee x_{1}) \wedge (\neg y_{1} \vee \neg x_{1}) \wedge \\ (y_{1} \vee x_{2}) \wedge (\neg y_{2} \vee \neg x_{2})\wedge \\ (y_{1} \vee x_{3}) \wedge (\neg y_{3} \vee \neg x_{3})
are both unsatisfiable.

The reduction:
In the following reduction we are given an instance of 3SAT,
F = \wedge_{i=1}^{n} C_{i}. Here each clause is of the form:
C_{i} = x_{i1} \vee ... \vee x_{ik_i} where
k_{i} < 4
and each x_{ik_i} is a literal of the form \neg z_{l} \ or \ z_{l} .
We use the following construction to build an instance of Monotone  3 SAT out of the above instance of 3SAT :
In each clause C_{i} we have at most one literal, z_{l} \ or \ \neg z_{l} that is not of the same parity as the rest of the literals in the clause. For every such literal, we may preform the following substitution:
z_{l} \rightarrow \neg y_{l} \ or \ \neg z_{l} \rightarrow y_{l} this yields a modified clause C'_{i}.
Now we must be able to guarantee that z_{l} and y_{l} are mapped to opposite truth values, so we introduce the new clause:
C''_{i} \ = \ ( z_{l} \vee y_{l}) \wedge ( \neg z_{l} \vee \neg y_{l}) and conjunct it onto our old formula F producing a new formula F'.

For example:
C_{i} \ = \ (z_{l_1} \vee z_{l_2} \vee \neg z_{l_3}) so we preform the substitution
\neg z_{l_3} \rightarrow y_{l_3}
so C'_{i} \ = \ (z_{l_1} \vee z_{l_2} \vee y_{l_3}) and C''_{i} \ = \ (z_{l_3} \vee y_{l_3}) \wedge ( \neg z_{l_3} \vee \neg y_{l_3})

Now repeating this procedure will result in a new formula: F' = (\wedge_{i=1}^{n} C'_{i}) \wedge (\wedge_{k=1}^{m} C''_{k}).
We claim logical equivalence between the C_{i} \wedge C''_{i} and C'_{i} \wedge C''_{i} This is semantically intuitive as the C''_{i} clause requires all substituted literal y_{l} in C'_{i} to take the value opposite of z_{l} this was the stipulation for the substitution initially. It is also verifiable by truth table construction for:
\\ (z_{l_1} \vee z_{l_2} \vee \neg z_{l_3}) \wedge (z_{l_3} \vee y_{l_3}) \wedge ( \neg z_{l_3} \vee \neg y_{l_3}) \Leftrightarrow \\  (z_{l_1} \vee z_{l_2} \vee y_{l_3}) \wedge (z_{l_3} \vee y_{l_3}) \wedge ( \neg z_{l_3} \vee \neg y_{l_3})

True_{3SAT} \Rightarrow True_{Monotone \ 3 \ SAT}:
If there exists a truth assignment \phi_{F} that satisfies F, then we may extent this truth assignment to produce \phi_{G} which will satisfy
G = F \wedge (\wedge_{k=1}^{m} C''_{k}) by letting \phi_{G} (z_{l}) = \phi_{F} (x_{l}) for all l and letting \phi_{G}(y_{l}) = \neg \phi_{F}(z_{l}) for all l.
Obviously if F is satisfiable G must be by the above construction of \phi_{G}. So by the above claim we have that \phi_{G} will satisfy F'.
True_{Monotone \ 3 \ SAT} \Rightarrow True_{3SAT}:
Continuing from the above, if we have a truth assignment \phi_{F'} that satisfies F', then by the claim above it also must satisfy G. And F is a sub-formula of G so any truth assignment that satisfies G must also satisfy F.

(Back to me)

Difficulty: 4, since it’s a little harder than the regular Monotone Sat one.

Protected: Chinese Postman for Mixed Graphs

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

Protected: Multiple Choice Branching

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