Section 9.4 Turing Machines
777
Definition P
P is the collection of all sets recognizable by Turing machines in polynomial time.
Consideration of set recognition in our definition of P is not as restrictive as it
may seem. Because the Turing machine halts on all appropriate input, it actually
decides, by halting in a final or nonfinal state, whether the initial string was or was
not a member of the set. Many problems can be posed as set decision problems by
suitably encoding the objects involved in the problem.
For example, consider the Hamiltonian circuit problem (Section 7.2) of
whether a graph has a cycle that uses every node of the graph. We may define
some encoding process to represent any graph as a string of symbols. Strings that
are the representations of graphs become appropriate input, and we want to decide, given such a string, whether it belongs to the set of strings whose associated
graphs have Hamiltonian circuits. If we can build a Turing machine to make this
decision in polynomial time, then the Hamiltonian circuit problem belongs to P.
We noted in Section 6.2 that the Hamiltonian circuit problem is solvable by the
brute-force approach of tracing all possible paths, but this is an exponential solution
because of the number of paths. We said that there is no known efficient (polynomial)
algorithm to solve the Hamiltonian circuit problem, so we have no proof that the
Hamiltonian circuit problem belongs to P. But there is also no proof that the Hamiltonian circuit problem does not belong to P. Might a clever, efficient algorithm someday be found? To see why this is unlikely, we’ll consider a new kind of Turing machine.
Ordinary Turing machines act deterministically, due to our restriction that no
two quintuples begin with the same present state/present symbol pair. A relaxation
of this requirement results in a nondeterministic turing machine, which may
have a choice of actions at any step. A nondeterministic Turing machine recognizes a string on its tape if some sequence of actions leads to halting in a final state.
Definition NP
NP is the collection of all sets recognizable by nondeterministic Turing machines
in polynomial time. (NP comes from nondeterministic polynomial time.)
Although a set in P requires that a deterministic Turing machine be able to
make a decision (in polynomial time) about whether some string on its tape does
or does not belong to the set, a set in NP requires only that a nondeterministic
Turing machine be able to verify (in polynomial time) by a fortuitous choice of actions that an input string is in the set. Given a graph that has a Hamiltonian circuit,
for example, this fact can be confirmed in polynomial time by a nondeterministic
Turing machine that picks the correct path, so the Hamiltonian circuit problem
belongs to NP. Another way to think about a nondeterministic Turing machine is
to imagine “parallel processing.” At every clock pulse where there is a choice of
action, new versions of the machine are created, one for each possible action. For
the Hamiltonian circuit problem, there may be an exponential number of versions
created, but the one version tracing the Hamiltonian circuit can complete its path
through the graph in polynomial time.
If a Turing machine can decide in polynomial time whether an arbitrary string
belongs to a set, it can surely use the same process to verify a member of the set
in polynomial time. Therefore P 8 NP. However, it is not known whether this
777
Definition P
P is the collection of all sets recognizable by Turing machines in polynomial time.
Consideration of set recognition in our definition of P is not as restrictive as it
may seem. Because the Turing machine halts on all appropriate input, it actually
decides, by halting in a final or nonfinal state, whether the initial string was or was
not a member of the set. Many problems can be posed as set decision problems by
suitably encoding the objects involved in the problem.
For example, consider the Hamiltonian circuit problem (Section 7.2) of
whether a graph has a cycle that uses every node of the graph. We may define
some encoding process to represent any graph as a string of symbols. Strings that
are the representations of graphs become appropriate input, and we want to decide, given such a string, whether it belongs to the set of strings whose associated
graphs have Hamiltonian circuits. If we can build a Turing machine to make this
decision in polynomial time, then the Hamiltonian circuit problem belongs to P.
We noted in Section 6.2 that the Hamiltonian circuit problem is solvable by the
brute-force approach of tracing all possible paths, but this is an exponential solution
because of the number of paths. We said that there is no known efficient (polynomial)
algorithm to solve the Hamiltonian circuit problem, so we have no proof that the
Hamiltonian circuit problem belongs to P. But there is also no proof that the Hamiltonian circuit problem does not belong to P. Might a clever, efficient algorithm someday be found? To see why this is unlikely, we’ll consider a new kind of Turing machine.
Ordinary Turing machines act deterministically, due to our restriction that no
two quintuples begin with the same present state/present symbol pair. A relaxation
of this requirement results in a nondeterministic turing machine, which may
have a choice of actions at any step. A nondeterministic Turing machine recognizes a string on its tape if some sequence of actions leads to halting in a final state.
Definition NP
NP is the collection of all sets recognizable by nondeterministic Turing machines
in polynomial time. (NP comes from nondeterministic polynomial time.)
Although a set in P requires that a deterministic Turing machine be able to
make a decision (in polynomial time) about whether some string on its tape does
or does not belong to the set, a set in NP requires only that a nondeterministic
Turing machine be able to verify (in polynomial time) by a fortuitous choice of actions that an input string is in the set. Given a graph that has a Hamiltonian circuit,
for example, this fact can be confirmed in polynomial time by a nondeterministic
Turing machine that picks the correct path, so the Hamiltonian circuit problem
belongs to NP. Another way to think about a nondeterministic Turing machine is
to imagine “parallel processing.” At every clock pulse where there is a choice of
action, new versions of the machine are created, one for each possible action. For
the Hamiltonian circuit problem, there may be an exponential number of versions
created, but the one version tracing the Hamiltonian circuit can complete its path
through the graph in polynomial time.
If a Turing machine can decide in polynomial time whether an arbitrary string
belongs to a set, it can surely use the same process to verify a member of the set
in polynomial time. Therefore P 8 NP. However, it is not known whether this