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.

One can write out an integral whose solution gives the number of solutions to the NP-Complete Number Partition Problem and I'm wondering if anyone has an suggestions or ideas on who to solve or approximate this integral analytically or numerically.

Given $a_0, a_1, \dots, a_{n-1} \in \mathbb{Z}$, the Number Partition Problem asks for a partition of the $a_k$'s such that $\sum_{k=0}^{n-1} \sigma_k a_k = 0$, where $\sigma_k \in \{ -1,1 \} $.

Consider the following Integral:

$$ I(a_0, a_1, \dots, a_{n-1}) = \frac{1}{2 \pi} \int_{-\pi}^{\pi} \prod_{k=0}^{n-1} (e^{ i a_k \theta } + e^{ -i a_k \theta } ) d\theta $$

$I(\dots)$ will count the number of solutions for a given instance of $(a_0, a_1, \dots, a_{n-1})$. Solving this integral is worse than NP-Hard (it's #P) so asking for a general solution is out of the question. But can one do any sort of approximation, either analytically or numerically? If you choose the $a_k$'s with some distribution, say uniform on some interval, can you exploit that randomness to help you approximate this integral?

Any ideas would be appreciated.

note: This has been studied by Borgs et all for the NPP Phase Transition and that's where I first saw this integral representation of the Number Partition Problem, but their analysis relies on approximating the family of instances given a uniform distribution on the $a_k$'s rather than trying to solve a particular instance, as I'm trying to do above.

share|improve this question
1  
I do not see the point of crossposting a question like this. Answers improve one another if everyone can see everyone else's answers; insights from different answers can be combined. Splitting up the answers like this seems counterproductive to me. –  Qiaochu Yuan Dec 3 '10 at 17:12
    
There was one answer from the mathoverflow site, otherwise it is essentially unanswered. Should I add a comment on what has been suggested already? –  user4143 Dec 3 '10 at 17:17
1  
Depending on how big the $a_k$ are and how many terms that product has, the integrand can be violently oscillatory, and quite a lot of the usual numerical methods will have trouble with this. Turning this into a contour integral might make it slightly more tractable, though. –  J. M. Dec 4 '10 at 13:17
    
@J.M., Mertens and later Borgs, Chayes and Pittel considered used the method of stationary phase to approximate the above integral when $a_k$'s are replace with the random variable $X_k$, but I do not see how to exploit this to solve the above integral. –  user4143 Dec 4 '10 at 16:11
    
Presumably if $\theta$ goes from $-\pi$ to $\pi$, you don't need the additional $2\pi$ in the exponents. –  mjqxxxx Jan 20 '11 at 16:06
show 3 more comments

1 Answer

Using a discrete Fourier transformation seems more appropriate if the $a_i$ are integers. The number of solutions is the value of the convolution product $$ \left(\delta_{a_0} + \delta_{-a_0}\right) * \left(\delta_{a_1} + \delta_{-a_1}\right) * ... * \left(\delta_{a_{n-1}} + \delta_{-a_{n-1}}\right) $$ evaluated at 0. This has the obvious dynamic programming solution, which takes something like $O(n A)$ time, where $A = \sum_i |a_i|$; i.e., it is a quasi-polynomial-time algorithm. If the $a_i$ are chosen at random from (bounded) distributions of integers instead, then the dynamic programming solution takes $O(n A^2)$ to calculate the expected number of solutions. The discrete Fourier transform translates that problem to a direct product of $n$ functions over $O(A)$ points, each of which can be computed in $O(A \log A)$ using the FFT, reducing the total time to $O(nA \log A)$. Moreover, the number of "approximate" partitions, i.e., choices of the $\sigma_i$ such that $|\sum_{i=0}^{n-1}\sigma_i a_i| \le k$ for some small $k$, falls out of this calculation essentially for free.

share|improve this answer
    
This is very much like the argument made by Mertens (see here). The difference in the analysis I presented and considering them as delta functions are very similar. I should have mentioned that the numbers under consideration are extremely large ($A = 2^m$, where $m$ is within polynomial factor of $n$) and so the order of the dynamic programming solutions becomes exponential. I was asking for efficient (approximate) algorithms when the elements are drawn from this (uniform) exponential distribution. –  user4143 Jan 21 '11 at 0:24
add comment

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.