Tag Archives: Difficulty 9

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

Open Hemisphere

I’m going to be out of town for the next 2 weeks, so we’ll be going on a bit of a hiatus.

The problem: Open Hemisphere.  This is problem MP6 in the appendix.

The description: Given a set X of m-tuples of integers, and a positive number K, can we find an m-tuple  \bar{y} of rationals such that at least K of the m-tuples, when multiplied by \bar{y}, are at least 0?

Example: Suppose our tuples were:

  1. {1,1,1}
  2. {-1,-1,-1}
  3. {1,-1,1}
  4. {-1,1,-1}

If K = 2, we can choose \bar{y} to be {1,0,1}.  This multiplied by tuples 1 and 3 would be positive (with a value of 2).  We could have also chosen {-1,0,-1} to make the multiplication with tuples 2 and 4 positive.  I don’t think there is a legal \bar{y} if K=3.  There certainly isn’t if K=4 (you can’t make both tuple 1 and tuple 2 positive simultaneously).

Reduction: Johnson and Preparata use Max-2-Sat.   So we’re given a 2-Sat instance with s clauses, m variables, and a target N, the number of clauses we need to satisfy.  Let t = \lceil log_{2}(ms+1) \rceil and d = m+1+3t.  We will create d-tuples as follows.

  • “A” vectors: 23t copies of “positive” and “negative” vectors for each variable.  So variable i has vectors Ai = i-1 0’s, followed by 1 followed by m-i 0’s, followed by 1, followed by each permutation of 1 or -1 of length 3t.  ~Ai is similar, except the first 1 is replaced by a -1.
  • 2t “B” vectors for each variable (positive and negative).  So variable i has vectors Bi = i-1 0’s, followed by 4, followed by m-i 0’s followed y -2, followed by 2t 0’s, followed by each permutation of 1 or -1 of length t.  ~Bi is similar, but the 4 is replaced by -4.
  • One “C” vector for each clause.  If the clause had variables xi and xj, the clause would be: i-1 0’s followed by 4*the sign of xi, followed by j-1 0’s, followed by 4* the sign of xj followed by m-j 0’s followed by 1 followed by 3t 0’s.

By “the sign of xi“, I mean 1 if xi shows up as a positive literal, and -1 if it shows up as a negated literal.  It’s also worth noting that since t is based on the log of the input size, creating a number of vectors that is exponential in t still keeps the input size of our hemisphere instance polynomial.

Our K will be 2m+23t+m*2t+N.  (All of the A tuples, half of the B tuples, and N of the C tuples)

If we have a Max-2-Sat solution, here’s how you build the \bar{y}:

  • Positions 1-m correspond to variables.  If the variable is set positively, put a 1 in that position.  If the variable is set negatively, put a -1 in that position.
  • Put a 1.5 in position m+1
  • Put a 0 everywhere else.

This will multiply positively with all A tuples, half of the B tuples, and  N of the C tuples.

If we have a hemisphere solution, it has to fit certain criteria:

  • At least 2m*23t-22t of the A vectors multiply positivly with our solution (this is how many you need even if all B and C vectors multiply positively)
  • Position m+1 of the solution vector is > 0 (otherwise not enough A vectors are positive)
  • At most 2t Bi vectors multiply positively with our solution for each variable i.  (Position m+1 of the B vector is the -2.  If we have more than 2t Bi vectors we’ll set position m+1 in the solution vector negative)
  • Position m+1 of the solution vector is  at least as big as the sum of the absolute values of the values in positions m+2+2t through m+1 + 3 (If it wasn’t, the limit on the B vectors would mean we wouldn’t be able to take enough A vectors to get a hemisphere solution)
  • Each value in the first m positions in the solution vector is at least as big as the absolute value of (position m+1) /4  (You can prove this by contradiction using algebra).  Importantly, this means those values can’t can’t be 0.
  • We must have at least N C tuples that multiply positively with the solution vector (given the limits on A and B).

Using these facts, we can find the ways to set the variables: Each of the first m positions in the solution vector correspond to a variable.  If the value at that position is positive, set it to true, if the value is negative, set it to false.  This will satisfy the N clauses that correspond to the C tuples that were made positive in the hemisphere solution.

Difficulty: 9.  Notice how much work has to happen to get around the fact that the hemisphere could have rational answers.  Also, notice how many tuples you need to get this reduction.  I’m also not 100% convinced yet that there isn’t a hole in the various claims about how the hemisphere solution has to behave that allows some weird combination of values to fall through.

Protected: Cost-Parametric Linear Programming

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: Register Sufficiency

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

Protected: Conjunctive Query Foldability

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

Protected: Additional Key

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

Protected: Prime Attribute Name

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

Protected: Rectilinear Picture Compression

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