How to integrate a polynomial over a simplex
How to integrate a polynomial over a simplex
This paper starts by settling the computational complexity of the problem of integrating a polynomial function $f$ over a rational simplex. We prove that the problem is $\mathrm {NP}$-hard for arbitrary polynomials via a generalization of a theorem of Motzkin and Straus. On the other hand, if the polynomial depends …