Tag Archives: Difficulty 9

Exponential Expression Divisibility

AN4 is Comparative Divisibility.

This next problem is related to one we’ve done before, but I think it merits its own entry.

The problem: Exponential Expression Divisibility.  This is problem AN5 in the appendix.

The description: Given two sequences A = a1..an and B=b1..bof positive integers, and an integer q. Does \prod_{i=1}^{n} (q^{a_{i}}-1) divide \prod_{i=1}^{m} (q^{b_{i}}-1)?

Let A={2,3} and B={1,4,5}.  If q=4, then the first product comes to 15×63=945 and the second product comes to 3x255x1023 = 782,595.  These two numbers don’t divide.

Reduction: Plaisted’s paper calls this a “refinement” of Polynomial Non-Divisibility.

The reduction for that built a polynomial called “Poly(Cj)”  and showed xN-1 is a factor of \prod_{j=1}^{k}Poly(~Cj)(x) if and only if S is inconsistent.  As I said in that post, there was a lot I don’t understand about it, because he doesn’t give clear proofs or explanations.  He uses some more manipulations to say that the SAT formula is inconsistent iff 2mn-1 divides \prod_{j=1}^{k} \frac{(2^{mn}-1) * Denom(C_j)(2^m)}{Num (C_j)(2*m)} .  (“Num” and “Den” were used in the creation of “Poly”).  This gives us a restatement of the Exponential Expression Divisibility problem where q =2.  Since there was nothing special about the 2, it could work for any integer and thus the reduction works in general.

Difficulty: 9.  Just like the Polynomial Non-Divisibility problem, I have a very hard time following what he’s doing here.  I wish I could find some better explanations

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.

Protected: Traveling Salesman Polytope Non-Adjacency

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

Protected: Open Hemisphere

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

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: