Problem Solving in Automata, Languages, and Complexity

304 COMPUTATIONAL COMPLEXITY

(b) Show that n3 is fully time-constructible.

4. (a) Show that if t(n) is fully time-constructible, then DTIME(t(n)) C -

DSPACE(t(n)).

(b) Show that if s(n) is fully space-constructible and s(n) > log n, then

DSPACE(s(n)) C - DTIME(2’*‘@)) for some constant C > 0.

5. Assume that A & B by a reduction function f with time bound 2”.

Also assume tha; B E DTIME (2n). What can you say about the time

complexity of set A?

6. Show that DSPACE(n(log* n)loo) $ DSPACE(nlogn).

7. Show that EXP : EXPPOLY.

8. Show that PSPACE $ Uc,o DSPACE(2’“).

6.4 Nondeterministic Turing Machines

In Chapters 2 and 3, we have seen that the notion of nondeterministic com-

putation is useful in the study of regular and context-free languages. In this

section, we introduce a new model of nondeterministic Turing machines, which

is critical to the theory of computational complexity. A one-tape nondeter-

ministic Turing machine (NTM) is like a one-tape DTM, except that at each

step, the machine may have more than one choice of possible next moves.

That is, the transition function 8 of a one-tape NTM M = (Q, C, I’, 6, qo) is a

mapping from Q x I’ to 2Qxrx(R,L), where 2’ denotes the set of all subsets

of strings,

Since an NTM may have more than one possible next move at each step, a

configuration may have more than one successor configuration. For instance,

if an NTM has tape symbol set I’, and an instruction

&,a) = {(Pl,bl,R),(P:!,b2,L),(P3,b3,R)},

then the configuration (q, zcady), - where X, y E I’* and c,d E I’, has three

successor configurations: (~1, zcbldy), (~2, z&dy), or (~3, zcbsdy). In other

words, the computation of an NTM is no longer a single path, but is a compu-

tation tree. Similar to NFA’s and PDA’s, we define that an NTM M accepts

an input X, if at least one computation path of the computation tree of M

on II= halts, that is, if the computation tree contains a leaf which is a halting

configuration. Equivalently, an NTM M accepts (x: if and only if there exists

a sequence of configurations (~Yo, al,... , a,), starting from the initial config-

uration ~XO = (s, Bd), ending at a halting configuration CY~ = (h, uav), such

that ai t-~~ ai+l for all i = 0, 1,... , nz - 1. Note that an NTM, unlike NFA’s

and PDA’s, may not halt on some inputs. It means that the computation tree

of an NTM may be infinite. Nonetheless, we say it accepts the input LC as long

as the computation tree has a finite path whose leaf is a halting configuration.

For an NTM M, we let L(M) be the set of all strings accepted by M.