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 $\mathrm{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 $\mathrm{}(Q>\mathrm{}2\mathrm{})\mathrm{}$ NPP exists, which could explain why it is so difficult to find good solutions for this case.