A fair split? Number partitioning

A group of N kids what to split up into two teams that are evenly matched. If the skill of each player is measured by an integer, can the kids be split into two groups such that the sum of the skills in each group is the same? This is the number partitioning problem, a classic and surprisingly difficult problem in computer science. In particular, it is NP-complete; it belongs to a category of problems for which no known algorithm can guarantee a resolution in a reasonable time (bounded by a polynomial in their size). Here we explore algorithms for solving the number partitioning problem, and find that the fiendishly difficult cases arise near a phase transition.

References

Links


James P. Sethna,

Last modified: August 24, 2006

Statistical Mechanics: Entropy, Order Parameters, and Complexity, now available at Oxford University Press (USA, Europe).