**The problem: **Number of Roots for a Product Polynomial. This is problem AN11 in the appendix.

**The description: **Given a set of sequences A_{1} through A_{m} , each A_{i} containing a sequence of k pairs through , and an integer K. If we build a polynomial for each A_{i} by , and then multiply all of those polynomials together, does the resulting product polynomial have less than K complex roots?

**Example: **Suppose A_{1} was <(1,2), (2,1), (1,0)>, A_{2} was <(3,3), (2,2), (1,1), (0,0)>, and A_{3} was <(5,1), (7,0)>. These represent the polynomials x^{2}+2x+1, 3x^{3} + 2x^{2} + 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 x^{6} + 61 x^{5} + 96 x^{4}+ 81 x^{3} + 50 x^{2} + 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 P_{C} and Q_{C} 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.