Tag Archives: 3SAT

Simultaneous Incongruences

Back to the problems we’ve skipped over, starting with a cool take on the classic “Chinese Remainder Theorem”.

The problem: Simultaneous Incongruences.  This is problem AN2 in the appendix.

The description: Given n pairs of positive integers (a1, b1)…(an, bn), can we find an integer x such that x \not\equiv ai mod bi?

(G&J also add the rule that  ai ≤ bi for all i, but we can easily make that happen by doing division)

Example: I think it’s easier to see this as the actual congruences:

Can we find an x such that:

  • x \not\equiv 1 mod 2
  • x \not\equiv 2 mod 3, and
  • x \not\equiv 3 mod 4?

If we chose x as 4, we’ll see that it works.  For a simple example of a case that fails, we can do:

  • x \not\equiv 1 mod 3
  • x \not\equiv 2 mod 3, and
  • x \not\equiv 3 mod 3

Reduction: I found this reduction in the Algorithmic Number Theory book by Bach and Shallit.  Their Theorem 5.5.7 calls this the “Anti-Chinese Remainder theorem”.  They reduce from 3SAT.

Our formula will have t variables and each clause in our formula is made up of 3 literals, which we’ll represent as Ci = (zai∨zbi∨zci).  For each ai find pai, the aith prime number, and find pbi and pci similarly.  Define ai‘ to be 0 if zai is a positive literal, and 1 if it’s a negative literal, and define bi‘ and ci‘ similarly.   Now for each clause, use the regular Chinese Remainder theorem to find a value xi where:

  • xi \equiv ai‘ mod pai
  • xi \equiv bi‘ mod pbi
  • xi \equiv ci‘ mod pci

Our system of incongruences will be:

  • x \not\equiv 2 (mod 3)
  • x \not\equiv 2,3 (mod 5)
  • x \not\equiv 2,3,4,…pt (mod pi)   (pt is the tth prime number)

The above incongruences are there to force x to be 0 or 1 mod each pi. I think these correspond to true-false values to the variables in the SAT instance (x being 0 mod pi means setting that variable false, making it 1 mod pi means setting that variable true)

  • x \not\equiv xi (mod pai*pbi*pci) for each i

This turns out to be O(n+t3) incongruences by the Prime Number Theorem.

Each clause in the SAT instance is satisfiable unless all 3 literals are false.  By the way we’ve created our ai‘  (and b and c), this means that the variables can’t be set to be equal to all of ai‘, bi‘ and ci‘.  Because of how our xi was chosen, this means that x is not congruent to xi (mod pai*pbi*pci).

Difficulty: 7.  This is a cool short reduction, but the way the x value works is something you don’t usually see.

Quadratic Congruences

On to the next section!  The “Algebra and Number Theory” section should take us through the end of the year.

The problem: Quadratic Congruences.  This is problem AN1 in the appendix.

The description: Given positive integers a,b, and c, can we find a positive integer x < c such that x2 ≡ a (mod b)?

Example: Let a = 3, b = 7, c = 13. It turns out that for every x < c, x2≡ either 0,1,2 or 4 mod b.   So this isn’t solvable.  But if we change a to 2, then the first c that works is 3.

One thing I learned in doing this problem is that the squares of mod b will always form a cycle with period b.  The proof is a pretty cool algebra problem if you set it up right.

Reduction: The paper by Manders and Adleman uses 3SAT.  Starting from the list of variables, they define a set Σ that holds all 3-element clauses of 3 different literals from that list of variables.  We won’t actually build this set (that’s exponential), but we can list out a number j for each of those clauses.  Then define τΦ to be -1* the sum of 8j for each of the j numbers that correspond to the clauses in our actual formula.

For each variable i, we define fi+ to be the sum of 8j for each j number in ∑ that has that variable positively, and fi to be -1* the sum of 8j for each number in Σ that has the variable negatively.

Let m be|Σ|, and set n=2m +The number of variables, and define a set C wit values c0 through cn:

  • c0 = 1
  • If j is odd(=2k-1) and ≤ 2m, cj = -8k/2
  • If j is even (=2k) and ≤ 2m, cj = -8k
  • If j is > 2m (= 2m+i), then cj = (fi++fi)/2

Set τ = τΦ + The sum of all of the ci‘s + The sum of all of the fi‘s.

This actually turns into a Subset Sum problem: Let C be our set, and count each value positively if we take it, and negatively if we don’t take it.

But we still need to prove this is SOS problem is solvable exactly when the original problem is.

Create a set p0 .. pn of consecutive prime numbers where the first one (p0) is 13.  Then define a set of θj values as the smallest number satisfying:

  • θj≡ ci (mod 8m+1)
  • θj ≡ 0 (mod The product of each (pi)n+1, except for j.)
  • θj is NOT ≡ 0 (mod pj)

Set H = The sum of all of the θj‘s.  Set L=the product of all of the (pi)n+1.  We are finally ready to create our Quadric Congruence instance:

b = 2*8m+1*K.

Let d = The inverse of (2*8m+1+K), mod b.

Then a = d*(K*τ2+2*8m+1 * H2)

c = H.

From here, it’s a bunch of algebra to show that an x exists if and only if the original formula was satisfiable.

Difficulty: 9.  Maybe it should be 10.  I don’t know enough number theory to be convinced that the θ’s exist, and be computed in polynomial time.  The algebra I’m glossing over is pretty complicated as well.

Traveling Salesman Polytope Non-Adjacency

This may be the hardest problem description to understand that I’ve done.  I’m still not sure I really understand the problem, let alone the reduction.  So I apologize in advance for what you’re about to read.

The problem: Traveling Salesman Polytope Non-Adjacency.  This is problem MP8 in the appendix.

The description:  I’ve got a lot of this definition from the paper by Papadimitriou that has the reduction.  We’ll take it slowly:

Suppose we have a complete, undirected, weighted graph G=(V, E).  Let |V| = n.  This means that |E| = n*(n-1)/2.  We can number these edges, and then denote whether a potential tour is “using” an edge or not by a 0/1 vector.  So a vector (0,1,1,0,1,0) means that the solution we’re considering uses edges 2,3, and 5.  (This may or may not be a legal tour).  Each legal Hamiltonian Cycle can be represented as one of these vectors.  This gives us a set of 0/1 vectors.  We can think of these vectors as points in Rn.  We then want to talk about the convex hull of these points.

Two vertices on this convex hull are defined to be “adjacent” if they are connected by an edge on the convex hull.

So, the problem asks: Given two Hamiltonian Cycles on G, are they non-adjacent on this convex hull?

(Yes, it’s weird that the problem never uses the distances between the vertices.  I think this is really “Hamiltonian Cycle Polytope Non-Adjacency”.  In fact, I think this makes more sense because the graph that is built in the reduction is not a complete graph)

Example: This is pretty hard to visualize, so let’s start with a simple graph:

Let’s list edges in alphabetical order in our vector. The vector will have 6 elements in alphabetical order: ab, ac, ad, bc, bd, cd

So the tours we have are:

  • ABCDA, represented as (1,0,1,1,0,1)
  • ABDCA, represented as (1,1,0,0,1,1)
  • ACBDA, represented as (0,1,1,1,1,0)

..and that’s really it.  All of the other tours are either reversals of the above (such as ADCBA), or an above tour shifted by starting at a different point (like BCDAB), which use the same edges and thus create the same vectors.

So, we are left with 3 points in 6-dimensional space.  Obviously, any 2 points in that space are adjacent.  If we start with a graph with 5 vertices:

we have 10 dimensions to our vector, for the edges ab, ac, ad, ae, bc, bd, be, cd, ce, and de. We also have 12 tour vectors. I won’t list them all, but for example, the tour ABCDEA would be represented by (1,0,0,1,1,0,0,1,0,1).  In this case, the need to define what the convex hull of those points are, and whether 2 tours are adjacent becomes harder to see.


Papadimitriou uses 3SAT.  So we’re given a set of m clauses over p variables, and we need to build a graph and two tours.  The graph he builds is made up of a series of widgets.  These widgets are designed to force certain edges to be used if the graph is to have a Hamiltonian Cycle.  The idea is that he constructs the widgets in a way that we can construct 2 cycles that are non-adjacent if and only if the formula was satisfiable.  So for example, here is his “exclusive or” subgraph (p. 316 of the paper):

In this subgraph, a Hamiltonian Cycle needs to go from u to u’ or v to v’ (it can’t do both, it can’t do neither).  By constructing ever-more complicated versions of this, he builds a graph.  Here’s how it looks for the formula B = (x1, x2, x3) ∧ (x1, x2, ~x3) ∧ (~x1, ~x2, ~x3) (p. 319 of the paper):

The bold lines in the figure above correspond to setting all variables to true.  There is also a circuit corresponding to making all variables false.  (We assume this satisfies at least one clause because if it didn’t, we have a Satisfiability instance where each clause has at least one positive literal, which is trivially satisfiable).  It turns out that every edge in this graph belongs to at least one of these two cycles.  For these two cycles to not be adjacent in the polytope, there needs to be some other circuit “between” them.  This circuit corresponds to a legal way to set all of the variables to make all clauses true.  If no such circuit exists (and the formula is not satisfiable), then the 2 tours are adjacent.

Difficulty: 9.  I can see what he’s doing, but I really have trouble following how he gets there.  Part of the difficulty with this problem is that it’s such a weird non-intuitive (to me) definition of “adjacency”.  I wonder if there is a better one out there.  Another source of difficulty is what I think of as confusion between TSP and HC.  The crazy widgets don’t help either.

Protected: Integer Programming

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

Protected: Deadlock Avoidance

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

Protected: Timetable Design

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

Protected: Single Execution Time Scheduling With Variable Number of Processors

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

Protected: Register Sufficiency

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

Protected: Linear Bounded Automaton Acceptance

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

Protected: Consistency of Database Frequency Tables

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