Monthly Archives: September 2018

Quadratic Diophantine Equations

Since this problem’s reduction is basically the same as last week’s, let’s skip ahead to it now.

The problem: Quadratic Diophantine Equations.  This is problem AN8 in the appendix.

The description: Given positive integers a,b, and c, can we find positive integers x and y such that ax2 + by = c?

Example: Let a=1, b = 2, and c=5.  Then we’re asking if positive integers x and y exists to solve x2 + 2y = 5.  This is true when x=1 and y = 2.  If we change b to 3, then there are no positive integers x and y where x2 + 3y = 5.  (y has to be positive, so the only y that has a chance of working is y=1, which would require x to be √2)

Reduction: This is in the same paper by Manders and Adleman that had the reduction for Quadratic Congruences.  In fact, the reduction is almost exactly the same.  We go through the same process of creating the Subset Sum problem, and build the same H and K at the end.  The only difference is the instance: We build the quadratic (K+1)3*2*8m+1*(H2-x2) + K(x2-r2)-2K*8m+1y = 0.  We can multiply out the vales to get a,b, and c.

The rest of the reduction uses similar crazy algebra to the last problem.

Difficulty: 9, for the same reasons last week’s problem was.

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.

Comparative Vector Inequalites

This problem has a typo in G&J.  I’ll explain it once I get through the problem description.

The problem: Comparative Vector Inequalities.  This is problem MP13 in the appendix.

The description: Given two sets of m-tuples, X and Y.  X and Y can possibly be of different sizes (but each tuple in X and Y is always of length m).  Can I find an m-tuple \bar{z} such that if there are K different tuples \bar{x_i} in X that satisfy \bar{x_i} \geq \bar{z}, then there are less than K tuples \bar{y_i} in Y that satisfy \bar{y_i} \geq \bar{z}?

An m-tuple \bar{u} is \geq an m-tuple \bar{v} if an only if each element of \bar{u} is \geq the correspoinding element of \bar{v}.

The typo in G&J is that they say that it’s ok for there to be K or less (instead of strictly less) tuples in \bar{y} that satisfy the inequality.  But my book has an “update” written on the inside back cover that says it’s wrong.

Example: Suppose X is:

x1 1 2 3
x2 4 5 6
x3 7 8 9

..and Y is:

y1 1 1 1
y2 4 4 4
y3 7 7 7

If we choose \bar{z} as (4,4,5), then both x2 and x3 are ≥ that in X, but only y3 is ≥ it in Y.

Reduction: G&J say to use Comparative Containment, which is a good choice.  Comparative Containment gives you two sets R and S that are subsets of some set U (we used X in that problem, but let’s call it U to reduce confusion with the X in this problem), each with weights.  In our Comparative Containment reduction, we reduced to a version where all of the weights were 1, so we’ll use that version here.  The problem then asks: can we find a subset U’ of U such that there are more sets in R that have U’ as a subset than there are sets in S that have U’ as a subset?

We’ll make a set of |U| tuples, where each element in X is a 0/1 vector corresponding to an element in R. So if U was the numbers from 1-10, and an element of R was {2,4,7}, the corresponding element of X would be:

{0,1,0,1,0,0,1,0,0,0}

We do something similar for Y, where tuples correspond to elements in S.

The \bar{z} we pick will correspond to our U’. For any tuple in X or Y to be ≥ \bar{z}, \bar{z} will have to consist of only 0’s and 1’s.  A tuple in X (or Y) is ≥ \bar{z} if it has 1’s in it in all of the places there are 1’s in \bar{z}, and possibly 1’s in other places too.  This means that the elements in U corresponding to the 1’s in \bar{z} are a subset of the corresponding element of R (or S).

So the \bar{z} vector corresponds to a subset U’ of U that is a solution to the Comparative Containment problem.

Difficulty: 4.  The reduction itself isn’t that hard since they’re basically the same problem.  But the problems themselves are a little hard to wrap your head around.

Partially Ordered Knapsack

Continuing our “Variants on the Knapsack Problem” theme..

The problem: Partially Ordered Knapsack.  This is problem MP12 in the appendix.

The description: Like usual, we’re given a set U, where each element u in U has positive integer size s(u) and value v(u), a maximum total size B, and a target total value K.  We also are given a partial order \lessdot on the elements of U, which we can represent as a directed acyclic graph.  Can we find a subset U’ of U where the total size of all elements in U’ is at most B, the total value of all elements in U’ is at least K, and for all elements u in U’, if some other u’ is  \lessdot u’, then u’ is also in U’?

Example: Suppose we have the following 3 elements:

Item 1 2 3
Profit 3 3 5
Weight 3 3 5

If B=6 and K=6, and there is no partial order, then taking items 1 and 2 make a valid solution.  But if we add the partial order graph:

Than taking either item 1 or 2 means we have to also take item 3, which makes our size too big.  So this version can’t be solved.

Reduction: G&J have this as a “no reference” reduction, but I found a paper by Johnson and Neimi that has it, and I’m glad I did because it’s pretty slick.  The reduction is from Clique, So we’re given an undirected graph G=(V, E) and an integer K.   We need to build a partial order DAG (where the vertices will be knapsack items), and also sizes and values for each item.

The DAG has a vertex for each vertex and edge in G  (I’ll be talking about these as “vertices from V” and “vertices from E”)  Edges in the DAG connect vertices from V to the vertices from E that are incident on that vertex.  So there is no path of length more than 1 in the partial order (no edges come out of the vertices from E).

Both the value and size of each vertex from V are |E|+1, and the value and size of each vertex from E are 1.

B’ and K’ will both be set to K(|E|+1) + K(K-1)/2.  It’s worth noting that the first half of that equation will be the total profits and sizes of K vertices from V, and the second half will be total profits and sizes of the edges connecting those vertices if they form a clique.

Suppose we have a clique in G.  Then all of the vertices in the clique, plus all of the edges in the clique form a solution to the partially ordered knapsack problem, as described above.

If we have a solution to the Partially Ordered Knapsack problem, that means we have a set of vertices that respects the partial order with total value at least K’ and total size at most B’.  Since the value and size of each vertex are the same, that means that the total value = the total weight = K’ = B’.  The only way to get that is if we have K vertices from V, and K(K-1)/2 vertices from E.  Since the partial order is built such that we can’t take a vertex from E without taking a vertex from V that is an endpoint of the vertex from E, this means that we have a set of K(K-1)/2 edges in E that all have endpoints in one of K vertices from V, which forms a clique.

Difficulty: 5.  I like how the formula for B’ in the reduction is one where you can easily see what all of the pieces of it are doing, and where they all come from.