INTRODUCTION: From the answer to this question I learned that deciding whether a definite integral is $0$ or not can be NP-complete, as the following integral representation of the Number Partition Problem shows.

Given $n$ numbers $(a_0,a_1,...,a_{n-1})$ in the range of $1$ to $M$, find whether the following integral is $0$ or not: $$ \frac{1}{2\pi}\int_{-\pi}^{\pi} \prod_{k=1}^{n-1} (e^{ia_k \theta} + e^{-ia_k \theta}) d\theta. $$

To see the reduction, notice that the only terms that survive the integration would be the ones where the exponent sum up to $0$ and this happens exactly when there is a bipartition of $(a_0,a_1,...,a_{n-1})$ where elements of the two parts sum up to the same number. The integral is therefore different from $0$ iff such partition exists; this implies that computing a definite integral is at least as hard as Partition, which is known to be NP-complete.

QUESTION: Assuming our machine is able to handle reals, I am now interested in proving (or disproving) the NP-hardness of the following problem

Let $p(x)$ be a polynomial on $\mathbb{R}$ of degree $n$. Decide whether the following integral is $0$ or not: $$ \int_0^1 \cos(p(x)) dx. $$

More in general, what are the techniques one usually uses in order to do reduction for the problem of finding whether a definite integral is $0$ or not on a specific class of functions?

NOTE: This question was also posted on Mathematics Stack Exchange but I guess that attempt was too optimistic.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.