On the Complexity of Interpolation by Polynomials with Non-negative Real Coefficients

In this paper, we consider interpolation by $\mathit{\text{completely}}\mathit{\text{monotonous}}$ polynomials (CMPs for short), that is, polynomials with non-negative real coefficients. In particular, given a finite set $S\subset {\mathbb{R}}_{>0}\times {\mathbb{R}}_{\ge 0}$, we consider $\mathit{\text{the}}\mathit{\text{minimal}}\mathit{\text{polynomial}}$ of $S$, introduced by Berg [1985], which is `minimal,’ in the sense that it is eventually majorized by all the other CMPs interpolating $S$. We give an upper bound of the degree of the minimal polynomial of $S$ when it exists. Furthermore, we give another algorithm for computing the minimal polynomial of given $S$ which utilizes an order structure on sign sequences. Applying the upper bound above, we also analyze the computational complexity of algorithms for computing minimal polynomials including ours.