Paul Du Bois
paul.dubois at gmail.com
Tue Dec 7 06:12:05 CET 2004
(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.
More information about the Python-list