Machines with Memory - Models of Computation: Exploring the Power of Computing - page 121

m −

01 2 1

b

Ta p e Un i t

Choice Input

Control

Unit

Figure 3.23 A nondeterministic Turing machine modeled as a deterministic one whose control
unit has an external choice input that disambiguates the value of its next state.

easy to verify: they can be verified in a polynomial number of steps by a choice input string of
polynomial length.
The class NP contains many important problems. The Traveling Salesperson Problem
(TSP) is in this class. TSP is a set of strings of the following kind: each string contains an
integer n , the number of vertices (cities) in an undirected graph G , as well as distances between
every pair of vertices in G , expressed as integers, and an integer k such that there is a path that
visits each city once, returning to its starting point (a tour ), whose length is at most k .A
verifier for TSP is an ordering of the vertices such that the total distance travel ed is no more

than k .Sincethereare n ! orderings of the n vertices and n ! is approximately √ 2 πnn n e −n ,a
verifier can be found in a number of steps exponential in n ; the actual verification itself can be
done in O ( n 2 ) steps. (See Problem 3.24 .) NP also contains many other important languages,
in particular, languages defining important combinatorial problems.
While it is obvious that P is a subset of NP , it is not known whether they are the same.
Since for each language L in NP there is a polynomial p such that for each string w in L
there is a verifying choice input c of length p (

) , a polynomial in the length of w ,the
number of possible choice strings c to be considered in search of a verifying string is at most
an exponential in

| w |

| w | . Thus, for every language in NP there is an exponential-time algorithm

to recognize it.
Despite decades of research, the question of whether P is equal to NP , denoted P = NP ,
remains open. It is one of the great outstanding questions of computer science today. The
approachtakentothisquestionistoidentify NP -complete problems (see Section 8.10 ), the
hardest problems in NP , and then attempt to determine problems whether or not such prob-
lems are in P .TSPisoneofthese NP -complete problems.

3.8 Universality of the Turing Machine
We show the existence of a universal Turing machine in two senses. On the one hand, we show
that there is a Turing machine that can simulate any RAM computation. Since every Turing