Insidious exponential integral

I hope that someone's up for the challenge; I'm attempting to solve this via computer:

\begin{equation} \int_{-\pi}^\pi{\displaystyle \frac{e^{i\cdot a\cdot t}(e^{i\cdot b\cdot t}-1)(e^{i\cdot c \cdot t}-1)}{(e^{i\cdot t}-1)(e^{i\cdot d \cdot t}+1)(e^{i\cdot f \cdot t}-1)} \dots dt} \end{equation}

I want to know if it's possible to break this up into simpler subproblems. You can use just about anything to do this, but there is one restriction. In computer science terms, I want this to be in $P$.

Let me try to explain. I don't want the work I have to do grow exponentially. For instance, if I break up the integral into two integrals, I don't want to double the amount of work I have to do. I don't want to dramatically increase the amount of work I have to do by breaking things apart, I want to keep things fairly fast.

EDIT I'd prefer to see integration techniques used for this.

Solution 1:

This is at least as hard as the Number Partition Problem (or the related Subset Sum) and is probably equivalent. The Number Partition Problem is NP-Complete so the solution to such an integral is, in general, probably not polynomial time solvable.

To see that it's at least as hard, I will consider a special case of your integral. First notice that:

$$ a_k \in \mathbb{N}, \ \ k \in [ 0, 1, \dots, n-1 ] $$

$$ \mathbb{I}_{\sigma, a} = \frac{1}{2 \pi} \int_{-\pi}^{\pi} e^{ i \theta \sum_{k=0}^{n-1} \sigma_k a_k } d\theta $$

for $ \sigma_k \in \{-1, 1\}$.

Notice that $\mathbb{I}_{\sigma, a}$ will be 1 if the sum $\sum_{k=0}^{n-1} \sigma_k a_k = 0$. Otherwise $\mathbb{I}_{\sigma, a}$ will be 0. This gives us an indicator function to test whether the configuration is perfect or not.

Define $Z_a$ as follows:

$$ Z_{ a } = \int_{-\pi}^{\pi} \prod_{k=0}^{n-1} ( e^{i \theta a_k} + e^{- i \theta a_k } ) d\theta = \int_{-\pi}^{\pi} e^{- i \theta \sum_{k=0}^{n-1} a_k } \prod_{k=0}^{n-1} (e^{ 2 i a_k } + 1 ) d\theta $$

and notice that $Z_a$ also equals the sum of all indicator functions:

$$ Z_a = \sum_{ <\sigma> } \mathbb{I}_{\sigma, a} $$

where $<\sigma>$ denotes all possible configurations of $ \sigma_k \in \{ -1, 1\}$.

$Z_a$ counts the number of solutions and is a special case of the integral you presented above. Were you to produce an algorithm to evaluate your integral in polynomial time, it could be applied to the above integral not just showing that $ P = NP \ $ but that the related counting problem is also in $P\ $ ($ \text{#} P = P $).

While this means that you probably cannot produce a polynomial time algorithm (in general) to solve your integral, it also means that you can probably adapt algorithms used to solve the Number Partition Problem (or Subset Sum) to provide a solution to the original integral. For the integral you presented there is a (what appears to me) small hurdle of having the denominators being other than one, but perhaps you could simplify by using continued fractions.

To my knowledge, the current 'state of the art' algorithm in solving the Number Partition Problem is the Complete Karmarkar Karp algorithm (CKK). See here, here and here for discussions and descriptions.

If you want further reference on the Number Partition Problem and its integral representation, see Borgs, Chayes and Pittel's paper "Phase transition and finite-size scaling for the integer partitioning problem".