Skip to main content
1 of 5
Ganesh
  • 627
  • 4
  • 14

An NP-hard $n$ fold integral

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. Given a rational $v\in [0,1]$.

Is deciding if $J=v$ 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$.

Ganesh
  • 627
  • 4
  • 14