Logo IMG
HOME > PAST ISSUE > May-June 2002 > Article Detail


The Easiest Hard Problem

Brian Hayes

Where the Hard Problems Are

To make sense of what's going on here, it's necessary first to be clear about what it means for a problem to be hard. Computer science has reached a rough consensus on this issue: Easy problems can be solved in "polynomial time," whereas hard problems require "exponential time." If you have a problem of size x, and you know an algorithm that can solve it in x steps or x2 steps or even x50 steps, then the problem is officially easy; all of these expressions are polynomials in x. But if your best algorithm needs 2x steps or xx steps, you're in trouble. Such exponential functions grow faster than any polynomial for large enough values of x.

The easy, polynomial-time problems are said to lie in class P; hard problems are all those not in P. The notorious class NP consists of some rather special hard problems. As far as anyone knows, solving these problems requires exponential time. On the other hand, if you are given a proposed solution, you can check its correctness in polynomial time. (NP stands for "nondeterministic polynomial"—although admittedly that's not much help in understanding the concept.)

Figure 4. Multiplicity of optimal partitions . . .Click to Enlarge Image

Where does number partitioning fit into this taxonomy? Both the greedy algorithm and Karmarkar-Karp have polynomial running time; they can partition a set of n numbers in less than n2 steps. For purposes of classification, however, these algorithms simply don't count, because they're not guaranteed to find the right answer. The hierarchy of problem difficulty is based on a worst-case analysis, which disqualifies an algorithm if it fails on even one problem instance. The only known method that does pass the worst-case test is the brute-force approach of examining every possible partition. But this is an exponential-time algorithm: Each integer in the set can be assigned to either of the two subsets, so that there are 2n partitions to be considered.

Partitioning is a classic NP problem. If someone hands you a list of n numbers and asks, "Does this set have a perfect partition?" you can always find the answer by exhaustive search, but this can take an exponential amount of time. If you are given a proposed perfect partition, however, you can easily verify its correctness in polynomial time. All you need to do is add up the two subsets and compare the sums, which takes time proportional to n.

Indeed, partitioning is not just an ordinary member of the class NP; it is one of the elite NP problems designated NP-complete. What this means is that if someone discovered a polynomial-time algorithm for partitioning, it could be adapted to solve all NP problems in polynomial time. Each NP-complete problem is a skeleton key to the entire class NP.

Given these sterling credentials as a hard problem, it's all the more perplexing that partitioning often yields so readily to simple and unsophisticated methods such as the greedy algorithm. Does this problem have teeth, or is it just a sheep in wolf's clothing?

comments powered by Disqus


Of Possible Interest

Computing Science: Computer Vision and Computer Hallucinations

Feature Article: In Defense of Pure Mathematics

Feature Article: Candy Crush's Puzzling Mathematics

Subscribe to American Scientist