3
$\begingroup$

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.

  • 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.2010-12-03
  • 0
    There was one answer from the mathoverflow site, otherwise it is essentially unanswered. Should I add a comment on what has been suggested already?2010-12-03
  • 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.2010-12-04
  • 0
    @J.M., [Mertens](http://www-e.uni-magdeburg.de/mertens/publications/npp1.pdf) 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.2010-12-04
  • 0
    Presumably if $\theta$ goes from $-\pi$ to $\pi$, you don't need the additional $2\pi$ in the exponents.2011-01-20
  • 0
    @mjqxxxx, Thanks for pointing that out. I've fixed it.2011-01-21
  • 0
    As J. M. says, the size of the $a_k$ is important here. What can you say about them? If they, or many of them, are big (say > 10), you may be able to use asymptotic methods, maybe combined with quadrature. PS: Do you mean $\sigma_k \in \{-1,+1\}$ in the second paragraph?2011-04-21
  • 0
    @Jitse, I was imagining $a_k$ to be extremely large, typically on the size of $2^n$. And $\sigma_k$ now reads correctly, thanks for pointing it out.2011-04-23

1 Answers 1