If we could build a machine that determines, for any Turing machine T and input W, whether T halts, then we could build the following impossible machine:

function Impossible: return LoopIfHaltsOnItself (LoopIfHaltsOnItself); function LoopIfHaltsOnItself (M): return LoopIfHalts (M, M); function LoopIfHalts (M, w): if WillHalt (M, w) then while true do {} else return false;

A *nondeterministic polynomial-time complete (NP-complete)* problem is one that
can be solved in polynomial time on a nondeterministic Turing machine, but apparently
requires exponential time on a deterministic Turing machine. Problems that require
exponential time are called *intractable.*

NP-complete problems can be reduced to one another in polynomial time, so if one such problem has a polynomial-time solution, they all do.

Copyright © 1996 by David Matuszek

Last modified Apr 24, 1996