The problem: Number of Roots for a Product Polynomial. This is problem AN11 in the appendix.
The description: Given a set of sequences A1 through Am , each Ai containing a sequence of k pairs through , and an integer K. If we build a polynomial for each Ai by , and then multiply all of those polynomials together, does the resulting product polynomial have less than K complex roots?
Example: Suppose A1 was <(1,2), (2,1), (1,0)>, A2 was <(3,3), (2,2), (1,1), (0,0)>, and A3 was <(5,1), (7,0)>. These represent the polynomials x2+2x+1, 3x3 + 2x2 + x, and 5x+7. (I’m pretty sure it’s ok for the sequences to be of different length, because we could always add (0,0) pairs to shorter sequences). This multiplies out to 15 x6 + 61 x5 + 96 x4+ 81 x3 + 50 x2 + 26x +7, which has 4 distint complex roots, according to Mathematica.
Reduction: This is another one that uses Plaisted’s 1977 paper. (It’s problem P4). He builds the polynomials PC and QC in the same way that he did in the reduction for Non-Divisibility of a Product Polynomial. One of the statements that he says is “easy to verify” is that The product of the Q polynomials for each clause has N (for us, K) zeroes in the complex plane if and only if the original 3SAT formula was inconsistent.
Difficulty: I’m giving all of these problems based on the polynomials that come from a formula an 8.