Phase Transition in the Number Partitioning Problem
- 16 November 1998
- journal article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 81 (20), 4281-4284
- https://doi.org/10.1103/physrevlett.81.4281
Abstract
Number partitioning is an NP-complete problem of combinatorial optimization. A statistical mechanics analysis reveals the existence of a phase transition that separates the easy from the hard to solve instances and that reflects the pseudo-polynomiality of number partitioning. The phase diagram and the value of the typical ground state energy are calculated.Comment: minor changes (references, typos and discussion of resultsKeywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Probabilistic analysis of the number partitioning problemJournal of Physics A: General Physics, 1998
- Statistical mechanics of the random-satisfiability modelPhysical Review E, 1997
- Entropy of theK-Satisfiability ProblemPhysical Review Letters, 1996
- Probabilistic analysis of optimum partitioningJournal of Applied Probability, 1986
- Ergodicity of the Coupling Constants and the Symmetric-Replicas Trick for a Class of Mean-Field Spin-Glass ModelsPhysical Review Letters, 1983