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 = a_{1}..a_{n} and B=b_{1}..b_{m }of positive integers, and an integer q. Does divide ?

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(C_{j})” and showed x^{N}-1 is a factor of Poly(~C_{j})(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 2^{mn}-1 divides . (“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