Problem: Given a multiset S of irreducible polynomials in Z[x], say YES if S can be partitioned into two nonempty multisets A and B such that both the product of all the elements of A and the product of all the elements of B are polynomials with non-negative coefficients. Say NO otherwise. Is this problem solvable in polynomial time ? Is it Np-complete ?

  • 1
    $\begingroup$ A heuristic that alas fails on some problem instances: Let $r_1<r_2<\dots<r_m$ be the real roots of the polynomials, in increasing order. Note that the sign of each polynomial is constant over $(r_i,r_{i+1})$. Pick arbitrary rational values $c_0,\dots,c_{m+1}$ such that $c_0<r_1<c_1<r_2<\dots<r_m<c_{m+1}$. Now find a way to partition $S$ into two multisets so that the product of polynomials in each multiset, when evaluated at every $c_i$, yields a non-negative number. This is a linear algebra problem over $GF(2)$. Finally, check whether this partition solves your original problem. $\endgroup$
    – D.W.
    Commented Jan 19, 2022 at 9:44
  • $\begingroup$ Cross-posted to mathoverflow.net/questions/414227/… $\endgroup$ Commented Jan 19, 2022 at 17:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.