[Overview] [Previous] [Next]

Halting Problem, P=NP?

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.