Phase Transition in the Number Partitioning Problem

Preprint

21 September 1998

preprint
Published by arXiv in arXiv

https://doi.org/10.48550/arXiv.cond-mat/9807077

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.

Keywords

PARTITIONING PROBLEM NUMBER
NUMBER PARTITIONING
MECHANICS ANALYSIS
PHASE TRANSITION
COMPLETE PROBLEM
STATISTICAL
TRANSITION

All Related Versions

Version 1, 1998-07-06, ArXiv
Version 2, 1998-08-04, ArXiv
Version 3, 1998-09-21, ArXiv
Published version: Physical Review Letters, 81 (20), 4281.

This publication has 0 references indexed in Scilit: