we guess the value of each x i and then evaluate e. This is essentially an O (n)
algorithm. As in Example 12.8, we have a deterministic exhaustive search
algorithm whose complexity is exponential and a linear-time nondeterministic
one. However, unlike Example 12.8, we do not know of any nonexponential
deterministic algorithm.
This example and Examples 12.7 and 12.8 suggest that complexity questions
are affected by the type of Turing machine we use and that the issue of
determinism versus nondeterminism is a particularly crucial one. Some general
conclusions consistent with these observations can be made.
Theorem 14.1
Suppose that a two-tape machine can carry out a computation in n steps. Then
this computation can be simulated by a standard Turing machine in O(n 2 ) steps.
Proof: For the simulation of the computation on the two-tape machine, the
standard machine keeps the instantaneous description of the two-tape machine
on its tape, as shown in Figure 14.1. To simulate one move, the standard
machine needs to search the entire active area of its tape. But since one move of
the two-tape machine can extend the active area by at most two cells, after n
moves the active area has a length of at most O(n). Therefore the entire
simulation can be done in O(n 2 ) moves.
Figure 14.1
This result is easily extended to more than two tapes (Exercise 6 at the end of
this section).
Theorem 14.2
Suppose that a nondeterministic Turing machine M can carry out a computation
in n steps. Then a standard Turing machine can carry out the same computation
in O (k an ) steps, where k and a are independent of n.
algorithm. As in Example 12.8, we have a deterministic exhaustive search
algorithm whose complexity is exponential and a linear-time nondeterministic
one. However, unlike Example 12.8, we do not know of any nonexponential
deterministic algorithm.
This example and Examples 12.7 and 12.8 suggest that complexity questions
are affected by the type of Turing machine we use and that the issue of
determinism versus nondeterminism is a particularly crucial one. Some general
conclusions consistent with these observations can be made.
Theorem 14.1
Suppose that a two-tape machine can carry out a computation in n steps. Then
this computation can be simulated by a standard Turing machine in O(n 2 ) steps.
Proof: For the simulation of the computation on the two-tape machine, the
standard machine keeps the instantaneous description of the two-tape machine
on its tape, as shown in Figure 14.1. To simulate one move, the standard
machine needs to search the entire active area of its tape. But since one move of
the two-tape machine can extend the active area by at most two cells, after n
moves the active area has a length of at most O(n). Therefore the entire
simulation can be done in O(n 2 ) moves.
Figure 14.1
This result is easily extended to more than two tapes (Exercise 6 at the end of
this section).
Theorem 14.2
Suppose that a nondeterministic Turing machine M can carry out a computation
in n steps. Then a standard Turing machine can carry out the same computation
in O (k an ) steps, where k and a are independent of n.