(warning: pedantic and off-topic response) NP-Complete does not mean "equivalent to the halting problem." It means "poly-time equivalent to any other NP-Complete problem".
NP-Complete problems are "only" exponential-time. The halting problem is much harder! And of course, just the fact that a problem is NP-complete doesn't mean that you can't construct algorithms that do a pretty good job a pretty good fraction of the time. -- http://mail.python.org/mailman/listinfo/python-list
