Skip to main content

## How to Integrate a Polynomial over a Simplex

- Author(s): Baldoni, Velleda
- Berline, Nicole
- De Loera, Jesus
- Köppe, Matthias
- Vergne, Michèle
- et al.

## Published Web Location

https://arxiv.org/pdf/0809.2083.pdfNo data is associated with this publication.

## Abstract

This paper settles the computational complexity of the problem of integrating a polynomial function f over a rational simplex. We prove that the problem is NP-hard for arbitrary polynomials via a generalization of a theorem of Motzkin and Straus. On the other hand, if the polynomial depends only on a fixed number of variables, while its degree and the dimension of the simplex are allowed to vary, we prove that integration can be done in polynomial time. As a consequence, for polynomials of fixed total degree, there is a polynomial time algorithm as well. We conclude the article with extensions to other polytopes, discussion of other available methods and experimental results.