Entropy-based analysis of the number partitioning problem
A. R. Lima, Márcio Argollo de Menezes · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · 2001
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.