A physicist's approach to number partitioning

The statistical physics approach to the number partioning problem, a classi cal NP-hard problem, is both simple and rewarding. Very basic notions and m ethods from statistical mechanics are enough to obtain analytical results f or the phase boundary that separates the "easy-to-solve" from the "hard-to- solve" phase of the NPP as well as for the probability distributions of the optimal and sub-optimal solutions. In addition, it can be shown that solvi ng a number partioning problem of size N to some extent corresponds to loca ting the minimum in an unsorted list of O(2(N)) numbers. Considering this c orrespondence it is not surprising that known heuristics for the partitioni ng problem are not significantly better than simple random search. (C) 2001 Elsevier Science B.V. All rights reserved.