<p>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 ?</p>

CC BY-SA 4.0
2022-01-19T09:44:22.247Z
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.
CC BY-SA 4.0
2022-01-19T17:27:56.897Z
Cross-posted to https://mathoverflow.net/questions/414227/partition-of-multisets-of-polynomials
Emil Jeřábek
<np-complete><polynomials><partition-problem>
Partition of multisets of polynomials
luciano
# Partition of multisets of polynomials

(Asked by: username_0 on 2022-01-19)

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 ?

**Tags:** np-complete, polynomials, partition-problem
> **Comments:**
> **username_1**: 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.  
> **username_2**: Cross-posted to https://mathoverflow.net/questions/414227/partition-of-multisets-of-polynomials  

---

## 0 answers

