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

NP ∪ coNP

PSPACE = NPSPACE

∩

NP coNP

NP coNP

L 2

PRIMALITY

P

NL

L

Figure 8.7 The relationships among complexity classes derived in this section. Containment is
indicated by arrows.

string. Thus, O ( r ( n )) cells are used on the work and enumeration tapes in this determinis-
tic simulation and L is in PSPACE .

An immediate corollary to this theorem is that NP ⊆ PSPACE . This implies that P ⊆

EXPTIME . However, as mentioned above, P is strictly contained within EXPTIME .
Combining these results, we have the following complexity class inclusions:

⊆ ⊆ ⊆ ⊆ ⊆ ⊆

L NL P NP PSPACE EXPTIME NEXPTIME

where PSPACE = NPSPACE .Wealsohave L 2

⊂ ⊂

EXPTIME ,which
follow from the space and time hierarchy theorems. These inclusions and those derived below
are shown in Fig. 8.7 .
In Section 8.6 we develop refinements of this partial ordering of complexity classes by using
the complements of complexity classes.
We now digress slightly to discuss space-bounded functions.

PSPACE ,and P

8.5.5 Space-Bounded Functions
We digress briefly to specialize Theorem 8.5.6 to log-space computations, not just log-space
language recognition. As the following demonstrates, log-space computable functions are com-
putable in polynomial time.

THEOREM 8.5.8 Let M be a DTM that halts on all inputs using space O (log n ) to process inputs
of length n .Then M executes a polynomial number of steps.
Proof In the proof of Corollary 8.5.1 the number of configurations of a Turing machine M
with input and output tapes and s work tapes is counted. We repeat this analysis. Let r ( n )