Deadlock detection

Paul Du Bois paul.dubois at
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 mailing list