# Partition of multisets of polynomials

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 ?

• 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.
– D.W.
Jan 19, 2022 at 9:44
• Cross-posted to mathoverflow.net/questions/414227/… Jan 19, 2022 at 17:27