MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
RSS
Logo IMG
HOME > PAST ISSUE > May-June 2002 > Article Detail

COMPUTING SCIENCE

The Easiest Hard Problem

Brian Hayes

One of the cherished customs of childhood is choosing up sides for a ball game. Where I grew up, we did it this way: The two chief bullies of the neighborhood would appoint themselves captains of the opposing teams, and then they would take turns picking other players. On each round, a captain would choose the most capable (or, toward the end, the least inept) player from the pool of remaining candidates, until everyone present had been assigned to one side or the other. The aim of this ritual was to produce two evenly matched teams and, along the way, to remind each of us of our precise ranking in the neighborhood pecking order. It usually worked.

None of us in those days—not the hopefuls waiting for our name to be called, and certainly not the two thick-necked team leaders—recognized that our scheme for choosing sides implements a greedy heuristic for the balanced number partitioning problem. And we had no idea that this problem is NP-complete—that finding the optimum team rosters is certifiably hard. We just wanted to get on with the game.

Figure 1. One perfect partition . . .Click to Enlarge Image

And therein lies a paradox: If computer scientists find the partitioning problem so intractable, how come children the world over solve it every day? Are the kids that much smarter? Quite possibly they are. On the other hand, the success of playground algorithms for partitioning might be a clue that the task is not always as hard as that forbidding term "NP-complete" tends to suggest. As a matter of fact, finding a hard instance of this famously hard problem can be a hard problem—unless you know where to look. Some recent results, which make use of tools borrowed from physics and mathematics as well as computer science, have now shown exactly where the hard problems hide.

The organizers of sandlot ball games are not the only ones with an interest in efficient partitioning. Closely related problems arise in many other resource-allocation tasks. For example, scheduling a series of jobs on a dual-processor computer is a partitioning problem: Sorting the jobs into two sets with equal running time will balance the load on the processors. Another example is apportioning the miscellaneous assets of an estate between two heirs.





» Post Comment

 

EMAIL TO A FRIEND :

Of Possible Interest

Perspective: Searching for Great Adventures

Computing Science: New Dilemmas for the Prisoner

Feature Article: Digital Forensics

Subscribe to American Scientist