17
$\begingroup$

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.

$\endgroup$
5
  • 6
    $\begingroup$ 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. $\endgroup$
    – Noah Stein
    Jun 28, 2013 at 12:53
  • $\begingroup$ @Kaveh, I am not clear about your comment. Could you elaborate it into an answer? $\endgroup$
    – Ganesh
    Jul 1, 2013 at 16:12
  • $\begingroup$ @Kaveh: Revised. $\endgroup$
    – Ganesh
    Jul 2, 2013 at 5:37
  • 2
    $\begingroup$ 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/… $\endgroup$ Jul 2, 2013 at 6:25
  • 2
    $\begingroup$ ...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? $\endgroup$ Jul 2, 2013 at 6:28

1 Answer 1

11
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @ Johan, thanks for the answer, esp. the last edit $\endgroup$
    – Ganesh
    Jul 9, 2013 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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