5
$\begingroup$

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.

$\endgroup$

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.