308 COMPUTATIONAL COMPLEXITYTime and Space Complexity of NTM’s. Now, we define the notion of
time and space complexity of an NTM. Note that the computation of an
NTM M on an input x may have many computation paths. Among these
computation paths, which one should we use to measure its time and space
complexity? We recall that the basic notion of a nondeterministic machine
is that it accepts an input as long as at least one of the computation paths
is an accepting path. So, following this spirit, we define that, if II: E L(M),
then TimeM (x) is the number of moves in the shortest accepting computation
path of A4 on x. That is, if the NTM iV is able to find (nondeterministically)
an accepting path for x in t moves, then TimeM < t. What about the
inputs x which are not in L(M)? W e note that, in order to determine that
x $ L(M), we need to examine all computation paths and be sure that all
of them halt and reject the input. However, if M does not accept x, then
some computation paths of M on x may be infinite. In that case, M cannot
determine that x e L(M) within any finite number of moves, as there are
always some computation paths that are still alive. Therefore, we simply let
TimeM (x) =^00 if M does not accept x (even if all rejecting paths are finite).
To define the space complexity of NTM’s, we restrict ourselves to one-
worktape NTM’s. Assume that M has one input tape and one work tape. If
x E L(M), then we let SpaceM(x) be the number of tape cells in the work
tape visited by M in the accepting computation path which uses the least
amount of space. (Note: The shortest accepting path that defines TimeM
and the least-space accepting path that defines spcq&x) are not necessarily
the same path.) If x 4 L(M), then again we let space,(x) = 00.
We say M has a time bound t(n) if TimeM 5 max(lx( + l,t(lxl)} for
all x E L(M), and M has a space bound s(n) if SpaceM(x) 5 max{l,s(12))}
for all x E L(M). Note that the above time and space bounds of an NTM
M depend only on strings in L(M). For instance, suppose that L(M) is
finite. Then, there exists a constant to such that TimeM < to for all
x E L(M). This implies that M has a time bound K(n), where>(n) is the
constant function such that K(n) = to (even though for sufficiently large n,
TimeM (x) = 00 for all x of length n, since they are all not in L(M)).
This definition can be justified as follows: Suppose that TimeM (x) 5 t (1x1)
for all x E L(M), and that t(n) is a fully time-constructible function. Then,
we can attach a (deterministic) t( n )- c oc 1 k machine to M and stops the com-
putation of M(x) after t(lxl) moves (and rejects if M(x) does not halt in
t(lxl) moves). Now, this new machine M’ accepts the same language as M
and TimeM/ < - t(lxl) f or all x. This shows that our definition of time
complexity of NTM’s is reasonable.
From the above complexity measures for NTM’s, we can define the nonde-
terministic complexity classes as follows.NTIME(t(n)) = {L(M) I M is an NTM with time bound t(n)}.
NSPACE(s(n)) = {L(M) ( M is an NTM with space bound s(n)}.