Blog on Math Blogs

Mathematical Digest

Short Summaries of Articles about Mathematics
in the Popular Press

"The Easiest Hard Problem," by Brian Hayes. American Scientist, March-April 2002, pages 113-117.

The problem in question is the balanced number partitioning problem: Separate a given a set of n positive integers into two subsets, so that the sums of the integers in the subsets are as close to one another as possible. Hayes introduces the problem by using the example of choosing up sides for a ball game, and later describes how it relates to statistical mechanics. He gives two algorithms for partitioning the numbers, but neither is guaranteed to find subsets with the closest sums. This leads to a discussion of P, NP and NP-complete. Hayes describes how the difficulty of the problem is connected to both the size of the set and the size of the numbers in the set. He concludes by explaining some of the current research associated with the problem.

---Mike Breen