An NP-hard $n$ fold integral

Question

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?

This question was originally posted CS.SE.

Answer 1

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.