The Easiest Hard Problem: Balanced Number Partitioning
americanscientist.org
americanscientist.org
Second, the article gives an example of a two-set partitioning problem and then states that "the only sure way to find the one perfect partition is to check all possible partitions", i.e., that the optimal algorithm runs in O(2^N) time. In fact, there is a trivial O(sqrt(2)^N) algorithm for the problem.
Going from the O(2^(N/2) N) algorithm described in the wikipedia article to O(2^(N/2)) just involves keeping the lists of subset sums sorted during the construction process, thereby avoiding the need for the expensive sorting step.
That said, the O(2^(N/2)) algorithm requires O(2^(N/2)) space, making it less than ideal; in most circumstances, an algorithm which generates the lists of subset sums for each half of the list on-demand using a priority queue is better -- this approach takes O(2^(N/2) N) time, but only O(2^(N/4)) memory.
Regardless, the most interesting aspect of the article to me was the existence of a phase transition between easy and hard parts of this type of problem. I found the reference to Stephan Mertens work relating this computational problem to statistical physics, specifically spin glasses, the most interesting. See samples of his work at http://arxiv.org/find/all/1/all:+AND+stephan+mertens/0/1/0/a...
Incidentally, Angell has a new paper out on the glass transition. http://arxiv.org/abs/0712.4233