Phase Transition in the Number Partitioning Problem

Stephan Mertens
Phys. Rev. Lett. 81, 4281 – Published 16 November 1998
PDFExport Citation

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.

  • Received 6 July 1998

DOI:https://doi.org/10.1103/PhysRevLett.81.4281

©1998 American Physical Society

Authors & Affiliations

Stephan Mertens*

  • Universität Magdeburg, Institut für Physik, Universitätsplatz 2, D-39106 Magdeburg, Germany

  • *Email address: Stephan.Mertens@Physik.Uni-Magdeburg.DE

References (Subscription Required)

Click to Expand
Issue

Vol. 81, Iss. 20 — 16 November 1998

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×