Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
6  
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
2  
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
2  
...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
add comment

1 Answer 1

up vote 11 down vote accepted

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.

share|improve this answer
    
@ Johan, thanks for the answer, esp. the last edit –  Ganesh Jul 9 '13 at 19:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.