Return to 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.

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.

Let $[c_1, c_2, \ldots, c_n]$ and $v$ are rational numbers in $[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.

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.

This question received no answers on CS.SE, and I thought MO (not M.SE nor CSTheory.SE) was the right place to ask, as it involves both integrals and complexity.

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 $$ \begin{align} I_1 = [0,1] \\ I_i = [\max(c_i,\theta_{i-1}),1] , 2\leq i\leq n \end{align} $$

and the $c_i \in [0,1]$ are predefined rational constants.

(Revised): Consider a problem instance whose inputs are the array $[c_2,\ldots, c_n]$ and a rational $v\in [0,1]$. The problem seeks to decide if $J$, computed with the given $c_i$'s,evaluates to $v$.

Is this problem 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$.

Updated from comments : Also, note that $J$ is the $n$-dimensional volume of some sort of polytope; possibly this is the union of an $n$-dimensional simplex with the hybercuboid whose edge lengths are the $c_i$'s. Perhaps this volume is NP-hard to compute using techniques from Computational Geometry?

Let $[c_1, c_2, \ldots, c_n]$ and $v$ are rational numbers in $[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.