Entropy-based analysis of the number partitioning problem.
In this paper we apply the multicanonical method of statistical physics on the number partitioning problem (NPP). This problem is a basic NP-hard problem from computer science, and can be formulated as a spin-glass problem. We compute the spectral degeneracy, which gives us information about the number of solutions for a given cost E and cardinality difference m. We also study an extension of this problem for Q partitions. We show that a fundamental difference on the spectral degeneracy of the generalized (Q>2) NPP exists, which could explain why it is so difficult to find good solutions for this case.
Lima
A R
AR
Laboratoire de Physique et Méchanique des Milieux Hétérogènes, ESPCI Paris, 10 rue Vauquelin, 75231 Paris Cedex 05, France. arlima@if.uff.br
Argollo de Menezes
M
M