Information Technology Reference
In-Depth Information
A precise Turing machine M is a multi-tape DTM or NDTM for which there is a func-
tion r ( n ) such that for every n
1, every input w of length n , and every (possibly nondeter-
ministic) computation by M , M halts after precisely r ( n ) steps.
We now show that if a total function can be computed by a DTM, NDTM, or OTM
within a proper time or space bound, it can be computed within approximately the same
resource bound by a precise TM of the same type. The following theorem justifies the use of
proper resource functions.
THEOREM 8.4.2 Let r ( n ) be a proper function with r ( n ) ≥ n .Let M be a multi-tape DTM,
NDTM, or OTM with k work tapes that computes a total function f in time or space r ( n ) .Then
there is a constant K> 0 and a precise Turing machine of the same type that computes f in time
and space Kr ( n ) .
Proof Since r ( n ) is a proper function, there is a DTM M r that computes its value from an
input of length n in time K 1 r ( n ) for some constant K 1 > 0andinspace r ( n ) .Wedesign
apreciseTM M p computing the same function.
The TM M p has an “enumeration tape” that is distinct from its work tapes. M p initially
invokes M r to write r ( n ) instances of the letter a on the enumeration tape in K 1 r ( n ) steps,
after which it returns the head on this tape to its initial position.
Suppose that M computes f within a time bound of r ( n ) . M p then alternates between
simulating one step of M on its work tapes and advancing its head on the enumeration
tape. When M halts, M p continues to read and advance the head on its enumeration tape
on alternate steps until it encounters a blank. Clearly, M p halts in precisely ( K 1 + 2 ) r ( n )
steps.
Suppose now that M computes f in space r ( n ) . M p invokes M r to write r ( n ) special
blank symbols on each of its work tapes. It then simulates M , treating the special blank
symbols as standard blanks. Thus, M p uses precisely kr ( n ) cells on its k work tapes.
Configuration graphs , defined in Section 5.3 , are graphs that capture the state of Turing
machines with potentially unlimited storage capacity. Since all resource bounds are proper, as
we know from Theorem 8.4.2 , all DTMs and NDTMs used for decision problems halt on all
inputs. Furthermore, NDTMs never give an incorrect answer. Thus, configuration graphs can
be assumed to be acyclic.
8.5 Classification of Decision Problems
In this section we classify decision problems by the resources they consume on deterministic
and nondeterministic Turing machines. We begin with the definition of complexity classes.
DEFINITION 8.5.1 Let r ( n ): ￿
be a proper resource function. Then TIME
(
r
(
n
))
and
SPACE
are the time and space Turing complexity classes containing languages that
canberecognizedbyDTMsthathaltonallinputsintimeandspace r ( n ) , respectively, where n is
the length of an input. NTIME
(
r
(
n
))
are the nondeterministic time
and space Turing complexity classes , respectively, defined for NDTMs instead of DTMs. The
union of complexity classes is also a complexity class.
(
r
(
n
))
and NSPACE
(
r
(
n
))
Let k be a positive integer. Then TIME ( k n ) and NSPACE ( n k ) are examples of complexity
classes. They are the decision problems solvable in deterministic time k n and nondeterministic
Search WWH ::




Custom Search