Complexity Classes - Models of Computation: Exploring the Power of Computing - page 337

Let r ( n ) and s ( n ) be proper functions. If for all K> 0thereexistsan N 0 such that
s ( n )

≥ Kr ( n ) for n ≥ N 0 , we say that r ( n )

is little oh of s

( n )

and write r ( n )= o ( s ( n )) .

THEOREM 8.5.2 (Space Hierarchy Theorem) If r ( n ) and s ( n ) are proper complexity func-
tions and r ( n )= o ( s ( n )) ,then SPACE ( r ( n )) is strictly contained in SPACE ( s ( n )) .

Theorem 8.5.3 states that there is a recursive but not proper resource function r ( n ) such
that TIME ( r ( n )) and TIME ( 2 r ( n ) ) are the same. That is, for some function r ( n ) there is a
gap of at least 2 r ( n )

r ( n ) in time over which no new decision problems are encountered.
This is a weakened version of a stronger result in [ 334 ] and independently reported by [ 51 ].

−

THEOREM 8.5.3 (Gap Theorem) Thereisarecursivefunction r ( n ): B ∗ →B ∗

such that

TIME ( r ( n )) = TIME ( 2 r ( n ) ) .

8.5.2 Time-Bounded Complexity Classes
As mentioned earlier, decision problems in P are considered to be feasible while the class
NP includes many interesting problems, such as the TRAVELING SALESPERSON problem,
whose feasibility is unknown. Two other important complexity classes are the deterministic
and nondeterministic exponential-time problems. By the remarks on page 336 , TRAVELING
SALESPERSON clearly falls into the latter class.

DEFINITION 8.5.3 The classes EXPTIME and NEXPTIME consist of those decision problems
solvable in deterministic and nondeterministic exponential time, respectively, on a Turing machine.
That is,

EXPTIME =
k≥

TIME ( 2 n k )

0

NEXPTIME =
k≥

NTIME ( 2 n k )

0

We make the following observations concerning containment of these complexity classes.

THEOREM 8.5.4 The following complexity class containments hold:

⊆ ⊆ ⊆

P NP EXPTIME NEXPTIME

⊂

However, P EXPTIME ,thatis, P is strictly contained in EXPTIME .

Proof Since languages in P are recognized in polynomial time by a DTM and such machines
are included among the NDTMs, it follows immediately that P ⊆ NP . By similar reasoning,

EXPTIME NEXPTIME .

Wenowshowthat P is strictly contained in EXPTIME . P

⊆

TIME ( 2 n ) follows be- ⊆

cause TIME ( n k ) TIME ( 2 n ) for each k

⊆ ≥ 0. By the Time Hierarchy Theorem (The-

orem 8.5.1 ), we have that TIME ( 2 n ) TIME ( n 2 n ) .But TIME ( n 2 n ) ⊂ ⊆ EXPTIME .

Thus, P is strictly contained in EXPTIME .
Containment of NP in EXPTIME is deduced from the proof of Theorem 5.2.2 by
analyzing the time taken by the deterministic simulation of an NDTM. If the NDTM
executes T steps, the DTM executes O ( k T ) steps for some constant k .