# An NP-hard $n$ fold integral

We are given rational numbers $[c_1, c_2, \ldots, c_n]$ and $v$ from the interval $[0,1]$.

Consider the $n$-fold integral $$J = \int_{\theta_1 \in I_1, \theta_2 \in I_2 \ldots, \theta_n \in I_n} d\theta_n\ldots d\theta_2 d\theta_1$$ whose intervals are defined by $$I_j = \begin{cases} [0,1] & j = 1\\ [\max(c_j,\theta_{j-1}),1] & 2\leq j\leq n \end{cases}$$ We want to check if $J$ is equal to $v$.

Is this problem $\mathsf{NP}$-hard?

Informally, each $\max$ in the lower limits of the intervals leads to a two-way split in evaluating the integral, and thus to $2^{n-1}$ integrals that sum to $J$.

Note that $J$ is also the volume of an $n$ dimensional polytope define by the following inequalities:

$$c_j \leq x_j \leq 1 \ (\text{for } 1 \leq j \leq n),$$ $$0 \leq x_1 \leq x_2 \leq \ldots \leq x_n \leq 1.$$

Is there a result in computational complexity or computational geometry about volume of such shapes?

-
Another way to think about this problem is computing the volume of the intersection of a simplex and a hypercube. This is a particular polytope defined by facets, but this is not immediately helpful because computing the volume of a polytope defined by facets is #P-hard in general, but this type of polytope could be easier. –  Noah Stein Jun 28 '13 at 12:53
@Kaveh, I am not clear about your comment. Could you elaborate it into an answer? –  Ganesh Jul 1 '13 at 16:12
@Kaveh: Revised. –  Ganesh Jul 2 '13 at 5:37
I just want to point out that the integral is essentially the same as the one that occurred in the question on "The Bruss-Yor conjecture about an iterated integral", mathoverflow.net/questions/100599/… –  Johan Wästlund Jul 2 '13 at 6:25
...only with the interval $[0,1]$ turned backwards, and general $c_i$. This is a different type of question, but is there a connection to the Last-Arrival problem? –  Johan Wästlund Jul 2 '13 at 6:28

The integral essentially asks for the probability that, for $n$ independent "events" uniformly distributed in $[0,1]$, at least one happens after $c_n$, at least two happen after $c_{n-1}$, etc (thinking of the unit interval as time). Let $P_n(c_1,\dots,c_n) = n!\cdot J$ denote this probability (the integral $J$ also requires the $n$ events to occur in a specified order).

If we condition on the number $k$ of events in the interval $[c_n,1]$, then the remaining events will be uniformly distributed in $[0,c_n]$, and we can write $P_n$ as $$P_n(c_1,\dots,c_n) = Pr(k=1)\cdot P_{n-1}\left(\frac{c_1}{c_n},\dots,\frac{c_{n-1}}{c_n}\right) + Pr(k=2)\cdot P_{n-2}\left(\frac{c_1}{c_n},\dots,\frac{c_{n-2}}{c_n}\right)+\dots.$$

To complete a recursive computation, we only need to compute the $O(n^2)$ integrals of the form $$P_i\left(\frac{c_1}{c_j},\dots,\frac{c_i}{c_j}\right)$$ for $1\leq i < j\leq n$. I'm not an expert on the complexity of rational arithmetic, but it seems to me that this should be doable in polynomial time.

EDIT:

Just for completeness, yes, the integral can be evaluated in $O(n^2)$ arithmetical operations, but so can $2^{2^n}$ (in fact in a linear number of operations), and that doesn't mean we can output (let alone compute) the digits in polynomial time. Even if the problem is to check an identity (so that the potential answer has to be part of the input), I don't see a general reason why that should be possible in polynomial time just because the number of arithmetical operations is polynomial (but people must have thought of that before, feel free to comment).

In this case however, the integral $P_n(c_1,\dots,c_n)$ is a degree $n$ polynomial in $c_1,\dots,c_n$, with coefficients that grow "only" exponentially. It follows that all the denominators (and numerators) of the partial results will have size (number of digits) polynomial in the size of the input.

-
@ Johan, thanks for the answer, esp. the last edit –  Ganesh Jul 9 '13 at 19:45