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


The Easiest Hard Problem

Brian Hayes

Antimagnetic Numbers

The ratio m/n divides the space of partitioning problems into two regions. Somewhere between them—between the fertile valley where solutions bloom everywhere and the stark desert where even one perfect partition is too much to expect—there must be a crossover region. There lies the phase transition.

The concept of a phase transition comes from physics, but it also has a long history of applications to mathematical objects. Forty years ago Paul Erdo?s and Alfred Rényi described phase transitions in the growth of random graphs (collections of vertices and connecting edges). By the 1980s, phase transitions had been observed in many combinatorial processes. The most thoroughly explored example is an NP-complete problem called satisfiability. A 1991 article by Peter Cheeseman, Bob Kanefsky and William M. Taylor, titled "Where the Really Hard Problems Are," conjectured that all NP problems have a phase transition and suggested that this is what distinguishes them from problems in P.

Meanwhile, in another paper with a provocative title ("The Use and Abuse of Statistical Mechanics in Computational Complexity"), Yaotian Fu of Washington University in St. Louis argued that number partitioning is an example of an NP problem without a phase transition. This assertion was disputed by Ian P. Gent of the University of Strathclyde and Toby Walsh of the University of York, who presented strong computational evidence for the existence of a phase transition. Their measurements suggested that the critical value of the m/n ratio, where easy problems give way to hard ones, is about 0.96.

Stephan Mertens, of Otto von Guericke Universität in Magdeburg, Germany, has now given a thoroughgoing analysis of number partitioning from a physicist's point of view. His survey paper (which has been my primary source in writing this article) appears in a special issue of Theoretical Computer Science devoted to phase transitions in combinatorial problems.

As a means of understanding the phase transition, Mertens sets up a correspondence between the number-partitioning problem and a model of a physical system. To see how this works, it helps to think of the partitioning process in a new context. Instead of unzipping a list of numbers into two separate lists, keep all the numbers in one place and multiply some of them by –1. The idea is to negate just the right selection of numbers so that the entire set sums to 0. Now comes the leap from mathematics to physics: The collection of positive and negative numbers is analogous to an array of atoms in a magnetic material, with the plus and minus signs representing up and down spins. Specifically, the system resembles an infinite-range antiferromagnet, where every atom can feel the influence of every other atom, and where the favored configuration has spins pointing in opposite directions.

This strategy for studying partitioning may seem slightly perverse. It takes a simply stated problem in combinatorics and turns it into a messy and rather obscure system in statistical mechanics. Why bother? The reason is that physics offers some powerful tools for predicting the behavior of such a system. In particular, the interplay of energy and entropy governs how the collection of spins can be expected to evolve toward a state of stable equilibrium. The energy in question comes from the interaction between atomic spins (or between positive and negative numbers); because the system is an antiferromagnet, the energy is minimized when the spin vectors are oppositely oriented (or when the subsets sum to zero). The entropy measures the number of ways of achieving the minimum-energy state; a system with a unique ground state (or just one perfect partition) has zero entropy. When there are many equivalent ways of minimizing the energy (or partitioning a set perfectly), the entropy is high.

The ratio m/n controls the state of this system. When m is much greater than n, the spins almost always have just one configuration of lowest energy. At the other pole, when m is much smaller than n, there are a multitude of zero-energy states, and the system can land in any one of them. Mertens showed that the transition between the two phases comes at m/n=1, at least in the limit of very large n. And he derived corrections for finite n that may explain why Gent and Walsh measured a slightly different transition point.

Finally, Mertens showed just how hard the hard phase is. Searching for the best partition in this region is equivalent to searching a randomly ordered list of random numbers for the smallest element of the list. Only an exhaustive traverse of the entire list can guarantee an exact result. What's worse, there are no really good heuristic methods; no shortcuts are inherently superior to blind, random sampling.

Yet this is not to say that heuristics for partitioning are totally worthless. On the contrary, the phase-transition model helps explain how the Karmarkar-Karp algorithm works. The differencing operation reduces the range of the numbers and so diminishes m/n, sliding the problem toward the easy phase. The algorithm can't be counted on to find the very best partition, but it's an effective way of avoiding the worst ones.

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