Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Have you tried standard numerical integration methods? –  Yuval Filmus Nov 25 '10 at 2:59
    
@Yuval:yes. They have potential; I'm not ruling them out if I can use them on subproblems. The main thing is that with these exponentials, everything seems to grow exponentially! Now I'm trying to see if breaking up the problem somehow can be competitive. –  Matt Groff Nov 25 '10 at 3:18
    
Your integrand has a number of singularities; can you guarantee that the integral is even bounded? –  Rahul Nov 25 '10 at 3:32
    
Yes. It's gauranteed that it will integrate to a positive integer or zero. In fact, I'd be satisfied (really elated!) if I could simply determine if the result is nonzero or not. –  Matt Groff Nov 25 '10 at 3:51
2  
What does "..." mean? I'm not sure how the pattern would continue. –  Hans Lundmark Nov 25 '10 at 5:45

2 Answers 2

Why don't you try complex integration ?. $\large z \equiv {\rm e}^{{\rm i}t}$. In order to accomplish this task we need to know anything about the constants $\left(a, b, \ldots\right)$.

share|improve this answer

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".

share|improve this answer
    
Matt happens to be attempting to use analytic techniques to solve P vs. NP, so I'm not surprised that this is true. –  Qiaochu Yuan Jan 28 '11 at 0:04

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.