Logo IMG
HOME > PAST ISSUE > March-April 2002 > Article Detail


The Easiest Hard Problem

Brian Hayes

Back to Mathematics

The work of Mertens has answered most of the major questions about number partitioning, and yet it's not quite the end of the story. The methods of statistical mechanics were developed as tools for describing systems made up of vast numbers of component parts, such as the atoms of a macroscopic specimen of matter. When applied to number partitioning, the methods are strictly valid only for very large sets, where m and n both go to infinity (while maintaining a fixed ratio). Those who need to solve practical partitioning problems are generally interested in somewhat smaller values of m and n.

Mertens's results have another limitation as well. In calculating the distribution of optimal solutions, he had to adopt a simplifying approximation at one crucial step, assuming that certain energies in the spin system are random. The true distribution of those energies is harder to deduce, but the task has been undertaken by Christian Borgs and Jennifer T. Chayes of Microsoft Research and Boris Pittel of Ohio State University. They have reclaimed the problem from the realm of physics and brought it back to mathematics. Their paper giving detailed proofs runs to nearly 40 pages.

To their surprise, Borgs, Chayes and Pittel discovered that Mertens's random-energy approximation actually yields exact results in the limiting case of infinite m and n. Under these conditions the phase transition is perfectly sharp. Anywhere below the critical ratio m/n=1, the probability of a perfect partition is 1; above this threshold the probability is 0. Borgs, Chayes and Pittel also give a precise account of how the phase transition softens and broadens for smaller problems. When n is finite, the probability of a perfect partition varies smoothly between 0 or 1, with a "window" of finite width surrounding the critical ratio.

If my friends and I back on the ball field had known all this, would we have played better games? Probably not, but in retrospect I take satisfaction in the thought that our ritual for choosing teams was algorithmically well-founded.

© Brian Hayes

comments powered by Disqus


Of Possible Interest

Computing Science: Computer Vision and Computer Hallucinations

Feature Article: In Defense of Pure Mathematics

Computing Science: Clarity in Climate Modeling

Subscribe to American Scientist