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).