Decomposition of polytopes and polynomials (Q5939542)

It was observed by \textit{A. Ostrowski} in Deutsche Math.-Ver. 30, 98--99 (1921; JFM 48.0106.01), that if a polynomial factors, then its Newton polytope decomposes, in the sense of the Minkowski sum, into the Newton polytopes of the factors. The authors present a ``pseudopolynomial-time'' algorithm [see \textit{M. R. Garey} and \textit{D. S. Johnson}, Computers and intractability: a guide to the theory of NP-completeness, Freeman, New York (1979; Zbl 0411.68039)] for testing indecomposability. Applications of the algorithms include absolute irreducibility testing and factorization of polynomials via their Newton polytopes.