Phase Transitions and Annealed Theories: Number Partitioning as a Case Study

We outline a technique for studying phase transition behaviour in computational problems using number partitioning as a case study. We first build an 'annealed' theory that assumes independence between parts of the number partition problem. Using this the theory, we identify a parameter which represents the ‘constrainedness’ of a number partition problem. We determine experimentally the critical value of this parameter at which a rapid transition between soluble and insoluble problems occurs. Finite-size scaling methods developed in statistical mechanics describe the behaviour around the critical value. We identify phase transition behaviour in both the decision and optimization versions of number partitioning, in the size of the optimal partition, and in the quality of heuristic solutions. This case study demonstrates how annealed theories and finite-size scaling allow us to compare algorithms and heuristics in a precise and quantitative manner