Now back to the problem we skipped over last week.
The problem: Non-Divisibility of a Product Polynomial. This is problem AN6 in the appendix.
The description: Just like Non-Trivial Greatest Common Divisor, we’re given a set of m sequences of pairs of integers (so sequence Ai is <(ai,bi) …(ai[k],bi[k])>), where each b element is ≥ 0. We’re also given an integer N.
Just like Non-Trivial Greatest Common Divisor, we build the polynomials , for each i from 1 to m. But now we want to multiply them all together. If we do, is the product not divisible by zN-1?
Example: Suppose A1 was <(1,3), (2,2), (-1,1), (-2,0)> and A2 was <(5,4), (3,2), (7,0)>. Then A1‘s polynomial is z3 + 2z2-z-2, and A2‘s polynomial is 5z4+3z2+7. The product of these is: 5z7+10z6 -2z5 – 4z4 + 4z3 + 8z2-7z-14. If N=2, then it turns out that z2-1 is a factor (it’s actualy a factor of A1), so the decision problem would say “No”.
Reduction: The reduction for this is again by Plaisted, using his polynomials that come from logical statements. For each clause C of a 3SAT formula, you build the polynomial PC for that clause, and from that QC = (xN-1)/PC He mentions in his paper that it is “easy to verify” (but doesn’t actually prove it) that The product of all of these QC‘s / (xN-1) is analytic iff S is inconsistent. I think the reason is that QC represents in his polynomial the ways to assign variables to make a formula false. So if all assignments make it false, the product is equal to all assignments. I still don’t quite see how the divisibility follows.
Difficulty: 8. It’s about as hard as the last one.