It is my understanding that the hard part is when m/n ~1 (P/N~1 in wikipedia terms). Does your O(sqrt(2)^N) algorithm work well for 1000 numbers between 1 and

It is my understanding that the hard part is when m/n ~1 (P/N~1 in wikipedia terms). Does your O(sqrt(2)^N) algorithm work well for 1000 numbers between 1 and 2^1000. Wikipedia says, "We give efficient algorithms for both small N and small P cases below," which would seem to imply the answer is no. 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/all/0/1 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 http://arxiv.org/abs/0712.4233