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^{ 2 \pi i a_k \theta } + e^{ -2 \pi 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.

$\endgroup$
2
  • $\begingroup$ Whenever I see a product of cosh's I think of the transfer matrix approach to the 1D Ising model. I wouldn't be surprised if you could map this integral onto something spin-glassy. $\endgroup$ Sep 10, 2010 at 1:41
  • $\begingroup$ As you mentioned, the $a_k$ are integers; what you then have is a product of cosines, and if the $a_k$ are large enough, the integrand is awfully oscillatory on the real line. Maybe you can either try finding a contour that bypasses these oscillations, or make use of specialized algorithms (e.g. those by Arieh Iserles) for handling finite oscillatory integrals. $\endgroup$ Sep 10, 2010 at 3:34

1 Answer 1

1
$\begingroup$

For any given $\theta$, Koksma's inequality should give you a relation between $(1/n)\sum_{k=0}^{n-1}\log(e^{2\pi ia_k\theta}+e^{-2\pi ia_k\theta})$ and $\int_0^1\log(e^{2\pi ix}+e^{-2\pi ix})dx$. The difference between them should be bounded by something depending on the discrepancy of the set of $a_k\theta$. Another relation is given by the Erdos-Turan inequality. Maybe one of these would be helpful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.