Entropy-based analysis of the number partitioning problem - art. no. 020106

In this paper we apply the multicanonical method of statistical physics on the number partitioning problem (NPP). This problem is a basic NP-hard prob lem from computer science, and can be formulated as a spin-glass problem. W e compute the spectral degeneracy, which gives us information about the num ber of solutions for a given cost E and cardinality difference m. We also s tudy an extension of this problem for Q partitions. We show that a fundamen tal difference on the spectral degeneracy of the generalized (Q>2) NPP exis ts, which could explain why it is so difficult to find good solutions for t his case.