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

be the maximum number of tape cells used and let c be the maximal size of a tape alphabet.
Then, M can be in one of at most χ

≤ c ( s + 2 ) r ( n ) ( nr ( n ) s + 1 )= O ( k r ( n ) ) configurations

for some k 1. Since M always halts, by the pigeonhole principle, it passes through at

most χ configurations in at most χ steps. Because r ( n )= O (log n ) , χ = O ( n d ) for some
integer d .Thus, M executes a polynomial number of steps.

≥

8.6 Complements of Complexity Classes
As seen in Section 4.6 , the regular languages are closed under complementation. However, we
have also seen in Section 4.13 that the context-free languages are not closed under comple-
mentation. Thus, complementation is a way to develop an understanding of the properties of
a class of languages. In this section we show that the nondeterministic space classes are closed
under complements. The complements of languages and decision problems were defined at
the beginning of this chapter.
Consider REACHABILITY . Its complement REACHABILITY is the set of directed graphs
G =( V , E ) and pairs of vertices u , v

V such that there are no directed paths between u
and v . It follows that the union of these two problems is not the entire set of strings over

∈

B ∗
but the set of all instances consisting of a directed graph G =( V , E ) and a pair of vertices
u , v V . This set is easily detected by a DTM. It must only verify that the string describing a

putative graph is in the correct format and that the representations for u and v are among the
vertices of this graph.
Given a complexity class, it is natural to define the complement of the class.

∈

DEFINITION 8.6.1 The complement of a complexity class of decision problems C , denoted
co

C C

, is the set of decision problems that are complements of decision problems in .

Our first result follows from the definition of the recognition of languages by DTMs.

THEOREM 8.6.1 If

C C = C

is a deterministic time or space complexity class, then co .

Proof Every L

∈ C

is recognized by a DTM M that halts within the res ource bound

for every string, whether in L or L , the complement of L .Create M f rom M by
complementing the accept/reject status of states of M 's control unit. Thus, L ,whichby
definition is in co

C

of

C C C ⊆ C C ⊆ co C C = C

,isalsoin .Thatis, co . Similarly, .Thus, co .

In particular, this result says that the class P is closed under complements. That is, if the
“yes” instances of a decision problem can be answered in deterministic polynomial time, then
so can the “No” instances.
We use the above theorem and Theorem 5.7.6 to give another proof that there are problems
that are not in P .

COROLLARY 8.6.1 There are languages not in P , that is, languages that cannot be recognized
deterministically in polynomial time.
Proof Since every language in P is recursive and

L 1 defined in Section 5.7.2 is not recursive,

L 1 is not in P .

it follows that

We now show that all nondeterministic space classes with a sufficiently large space bound
are also closed under complements. This leaves open the question whether the nondetermin-