Phase Transition in the Number Partitioning Problem

1998/07/31 by Stephan Mertens · 4 citations
Computer Science · Engineering · Physics and Astronomy · #Computational Geometry and Mesh Generation #Condensed matter physics #Optimization and Packing Problems #Phase (matter) #Phase transition #Physics #Quantum mechanics #Statistical physics #adap-org #cond-mat #nlin.AO #semigroups and automata theory

paper · pdf · doi:10.1103/physrevlett.81.4281

published as Phys.Rev.Lett. 81, 4281 (1998) · minor changes (references, typos and discussion of results)

arxiv created 1998/09/21 · openalex publication_date 1998/11/16 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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 pseudopolynomiality of number partitioning. The phase diagram and the value of the typical ground-state energy are calculated.

Citations

• A complete anytime algorithm for number partitioning
• Entropy of theK-Satisfiability Problem

Cited by

• Minimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picture
• Extreme value statistics and traveling fronts: Application to computer science
• Instance space of the number partitioning problem
• Partition problem [wikipedia]