Kozen D.C. Theory of Computation

Подождите немного. Документ загружается.

12 Lecture 2

Deﬁnition 2.2

DTIME(T (n))

def

= {L(M) | M is a deterministic multitape TM run-

ning in time T (n)},

NTIME(T (n))

def

= {L(M) | M is a nondeterministic multitape TM

running in time T (n)},

DSPACE(S(n))

def

= {L(M) | M is a deterministic TM with read-only

input tape and read/write worktape run-

ning in space S(n)},

NSPACE(S(n))

def

= {L(M) | M is a nondeterministic TM with read-

only input tape and read/write worktape

running in space S(n)}.

If A is a complexity class, the set of complements of sets in A is denoted

co-A. Note: this is not the complement of A!

Linear Speedup

The next result says that for the TM model, it does not make sense to

measure time and space complexity any more accurately than to within a

constant factor.

Theorem 2.3 Let T (n) ≥ n +1 and S(n) ≥ Ω(log n). For any constant c ≥ 1,

DTIME(cT (n)) ⊆ DTIME(T (n)),

NTIME(cT (n)) ⊆ NTIME (T (n)),

DSPACE(cS(n)) ⊆ DSPACE(S(n)),

NSPACE(cS(n)) ⊆ NSPACE(S(n)).

Proof sketch. Expand the tape alphabet so that c tape cells of the old

machine can be compressed into one tape cell of the new machine. This

allows c steps of the old machine to be simulated in one step of the new

machine. For the time bounds, we may need an extra tape to compress the

input. 2

Some Common Complexity Classes

Deﬁnition 2.4

LOGSPACE

def

= DSPACE(log n),

NLOGSPACE

def

= NSPACE(log n),

Time and Space Complexity Classes and Savitch’s Theorem 13

def

= DTIME(n

O(1)



k>0

DTIME(n

def

= NTIME(n

O(1)



k>0

NTIME(n

PSPACE

def

= DSPACE(n

O(1)



k>0

DSPACE(n

NPSPACE

def

= NSPACE(n

O(1)



k>0

NSPACE(n

EXPTIME

def

= DTIME(2

O(1)



k>0

DTIME(2

NEXPTIME

def

= NTIME(2

O(1)



k>0

NTIME(2

EXPSPACE

def

= DSPACE(2

O(1)



k>0

DSPACE(2

NEXPSPACE

def

= NSPACE(2

O(1)



k>0

NSPACE(2

Basic Inclusions

The inclusions

DTIME(T (n)) ⊆ NTIME (T (n)),

DSPACE(S(n)) ⊆ NSPACE(S(n))

are trivial, because by deﬁnition every deterministic TM is also a nonde-

terministic TM.

Theorem 2.5 Let S(n) ≥ log n.Then

DTIME(T (n)) ⊆ DSPACE(T (n)),

NTIME(T (n)) ⊆ NSPACE(T (n)),

DSPACE(S(n)) ⊆ DTIME (2

O(S(n))

NSPACE(S(n)) ⊆ NTIME(2

O(S(n))

Proof. The ﬁrst two inclusions follow from the fact that a machine can

scan at most one new worktape cell in every step, thus the space usage can

be no greater than the running time.

For the last two inclusions, we show how a machine running in space

S(n) can be modiﬁed to clock itself and shut down after 2

O(S(n))

steps

14 Lecture 2

without aﬀecting the set accepted. Assume without loss of generality that

the machine has a single read-only input tape and a single read/write work-

tape (multiple worktapes can be simulated on separate tracks of a single

worktape without loss of space by increasing the size of the worktape alpha-

bet). If the machine has d worktape symbols and q states, then there are

at most qnS(n)d

S(n)

possible conﬁgurations on inputs of length n, because

there are q possible states, n input head positions, S(n) worktape head

positions, and d

S(n)

worktape contents. This number is at most c

S(n)

for

some suﬃciently large constant c. Any computation path of length greater

than this must have a repeated conﬁguration, therefore there is a shorter

computation path with the same outcome (accept or reject) obtained by

deleting the segment between the two occurrences of the repeated conﬁgu-

ration. This says that if there exists an accepting computation path, then

there exists one of length at most c

S(n)

. We can count up to c

S(n)

on a

separate track of the worktape and reject if the simulated computation has

not halted by then. This takes no extra space if the counting is done in

c-ary,andthetimeoverheadisO(S(n)) steps per simulated step of the old

machine, or O(S(n)c

S(n)

) in all, which is still 2

O(S(n))

. 2

We can show an even stronger result that subsumes Theorem 2.5.

Theorem 2.6 Let S(n) ≥ log n.Then

NTIME(T (n)) ⊆ DSPACE(T (n)),

NSPACE(S(n)) ⊆ DTIME(2

O(S(n))

Proof. For the ﬁrst inclusion, we do a depth-ﬁrst search on the com-

putation tree of the given nondeterministic T (n)-time-bounded machine,

constructing the computation tree on the ﬂy. We accept if an accept con-

ﬁguration is ever encountered. It may seem at ﬁrst that we need O(T (n)

)

space to keep a stack of conﬁgurations for the depth-ﬁrst search, because

each conﬁguration requires up to T (n) space and the depth of the tree is

T (n); but actually we only need to keep on the stack a k-ary string giving

the path from the start conﬁguration to the conﬁguration currently being

visited, assuming that all nondeterministic choices are at most k-ary. We

can reconstruct the current conﬁguration in space T (n) at any time by

starting at the start conﬁguration and simulating the computation of the

nondeterministic machine, using the k-ary string to resolve nondeterminis-

tic choices.

For the second inclusion, assume ﬁrst that S(n)isspace-constructible.

That means that there exists a Turing machine that, when started with

any string of length n written on its input tape, marks oﬀ S(n) worktape

cells and halts, never using more than S(n) space in the process. Not all

functions are space-constructible, but the natural ones listed above are. We

show later how to get rid of this assumption.

Time and Space Complexity Classes and Savitch’s Theorem 15

Using the assumption of space-constructibility, we ﬁrst mark oﬀ S(n)

worktape cells. We then write down all the conﬁgurations of the nonde-

terministic machine that use no more than S(n) space. As argued in the

proof of Theorem 2.5, there are at most c

S(n)

of them, and we can write

themalldowninatmostS(n)c

S(n)

time. Now we inductively mark all

conﬁgurations that are reachable from the start conﬁguration, accepting if

we ever mark an accept conﬁguration. A coarse analysis of this procedure

still gives a time bound of d

S(n)

for suﬃciently large constant d.

To get rid of the space-constructibility assumption, instead of marking

oﬀ S(n) space initially, we do the entire procedure above for S =0, 1, 2,... .

For each S, if we ever encounter a conﬁguration reachable from the start

conﬁguration that wants to use more than S space, we set S := S +1 and

restart. We eventually hit S(n), at which point no reachable conﬁguration

will try to use more space. The time is at most

S(n)



S=0

≤

S(n)+1

− 1

d − 1

which is still 2

O(S(n))

. 2

Savitch’s Theorem

Probably the most important open question in theoretical computer science

is the P=NP question. The corresponding question for space was solved in

1970 by Walter Savitch [108]. This result is known as Savitch’s theorem.

Theorem 2.7 (Savitch’s Theorem) Let S(n) ≥ log n.Then

NSPACE(S(n)) ⊆ DSPACE(S(n)

In particular, PSPACE = NPSPACE .

Proof. We prove the result under the assumption that S(n) is space-

constructible. We can get rid of this assumption the same way as in Theo-

rem 2.6. By the construction of Theorem 2.5, we can also assume without

loss of generality that the given nondeterministic S(n)-space-bounded ma-

chine M is also d

S(n)

time-bounded for some constant d.

A conﬁguration of M consists of a state, head positions, and worktape

contents. The input string need not be explicitly represented. Encode con-

ﬁgurations of M as strings over a ﬁnite alphabet ∆ in some reasonable way,

and let d = |∆|. For inputs of length n, a conﬁguration of M is represented

byastringin∆

S(n)

,andthereared

S(n)

such strings. If α, β ∈ ∆

S(n)

,write

≤k

−→ β if α, β represent legal conﬁgurations of M and α goes to β in k

16 Lecture 2

or fewer steps according to the transition relation of M without exceeding

the space bound S(n).

The deterministic machine will implement a recursive procedure SAV

of three arguments α, β, k that determines whether α

≤k

−→ β.Notethatby

the pigeonhole argument of Theorem 2.5, if α

≤k

−→ β for any k at all, then

≤k

−→ β for some k ≤ d

S(n)

, so we can restrict our attention to numbers in

this range. Writing k in d-ary requires at most S(n) space.

Thus to determine whether M accepts x, it suﬃces to check whether

start

≤d

S(n)

−→ accept, where start and accept are the start and accept

conﬁgurations, respectively, which we can assume without loss of general-

ity are unique. The deterministic machine ﬁrst constructs S(n), then calls

SAV(start, accept,d

S(n)

The recursive procedure SAV(α, β, k)operatesasfollows.Ifk = 0 or 1,

it checks directly whether α = β or, in the case k =1,whetherα goes to

β in one step. It returns “yes” if so, otherwise it returns “no”. If k ≥ 2,

it loops through all γ ∈ ∆

S(n)

in some order, say lexicographic. For each

such γ, it calls SAV(α, γ, k/2) and SAV(γ,β,k/2) to determine whether

≤k/2

−→ γ and γ

≤k/2

−→ β, respectively. If both recursive calls return “yes”,

it returns “yes”. Otherwise, it goes on to the next γ. If it goes through all

γ without success, then it returns “no”.

This is a deterministic procedure. One can show easily by induction on

k that SAV(α, β, k) returns “yes” iﬀ α

≤k

−→ β. Each instantiation of SAV

requires a stack frame of size S(n) for preserving local data across recursive

calls. The stack can be kept on the worktape. The depth of the recursion

is log

S(n)

= O(S(n)), because k is halved with each recursive call. Thus

the total storage required is O(S(n)

). 2

Lecture 4

The Immerman–Szelepcs´enyi Theorem

In 1987, Neil Immerman [65] and independently R´obert Szelepcs´enyi [119]

showed that for space bounds S(n) ≥ log n, the nondeterministic space

complexity class NSPACE(S(n)) is closed under complement. The case

S(n)=n gave an aﬃrmative solution to a long-standing open problem of

formal language theory: whether the complement of every context-sensitive

language is context-sensitive.

Theorem 4.1 (Immerman–Szelepcs´enyi Theorem) For S(n) ≥ log n,NSPACE(S(n)) =

co-NSPACE(S(n)).

Proof. For simplicity we ﬁrst prove the result for space-constructible

S(n). One can remove this condition in a way similar to the proof of Sav-

itch’s theorem (Theorem 2.7).

The proof is based on the following idea involving the concept of a census

function. Suppose we have a ﬁnite set A of strings and a nondeterministic

test for membership in A. Suppose further that we know in advance the

size of the set A. Then there is a nondeterministic test for nonmembership

in A:giveny, successively guess |A| distinct elements and verify that they

are all in A and all diﬀerent from y. If this test succeeds, then y cannot be

in A.

Let M be a nondeterministic S(n)-space bounded Turing machine. We

wish to build another such automaton N accepting the complement of

The Immerman–Szelepcs´enyi Theorem 23

L(M). Assume we have a standard encoding of conﬁgurations of M over

a ﬁnite alphabet ∆, |∆| = d, such that every conﬁguration on inputs of

length n is represented as a string in ∆

S(n)

Assume without loss of generality that whenever M wishes to accept,

it ﬁrst erases its worktape, moves its heads all the way to the left, and

enters a unique accept state. Thus there is a unique accept conﬁguration

accept ∈ ∆

S(n)

on inputs of length n.Letstart ∈ ∆

S(n)

represent the

start conﬁguration on input x, |x| = n:inthestartstate,headsallthe

way to the left, worktape empty.

Because there are at most d

S(n)

conﬁgurations M can attain on input

x,ifx is accepted then there is an accepting computation path of length

at most d

S(n)

. Deﬁne A

to be the set of conﬁgurations in ∆

S(n)

that are

reachable from the start conﬁguration start in at most m steps; that is,

= {α ∈ ∆

S(n)

| start

≤m

−→ α}.

Thus A

= {start} and

M accepts x ⇔ accept ∈ A

S(n)

The machine N will start by laying oﬀ S(n) space on its worktape. It

will then proceed to compute the sizes |A

|, |A

|, ..., |A

S(n)

| in-

ductively. First, |A

| = 1. Now suppose |A

| has been computed and is

written on a track of N’s tape. Because |A

|≤d

S(n)

, this takes up S(n)

space at most. To compute |A

m+1

|, successively write down each β ∈ ∆

S(n)

in lexicographical order; for each one, determine whether β ∈ A

m+1

(the

algorithm for this is given below); if so, increment a counter by one. The

ﬁnal value of the counter is |A

m+1

|. To test whether β ∈ A

m+1

, nondeter-

ministically guess the |A

| elements of A

in lexicographic order, verify

that each such α is in A

by guessing the computation path start

≤m

−→ α,

and for each such α check whether α

≤1

−→ β.Ifanysuchα yields β in one

step, then β ∈ A

m+1

;ifnosuchα does, then β ∈ A

m+1

After |A

S(n)

| has been computed, in order to test accept ∈ A

S(n)

nondeterministically, guess the |A

S(n)

| elements of A

S(n)

in lexicographic

order, verifying that each guessed α is in A

S(n)

by guessing the computa-

tion path start

≤d

S(n)

−→ α, and verifying that each such α is diﬀerent from

accept.

The nondeterministic machine N thus accepts the complement of L(M)

and can easily be programmed to run in space S(n).

To remove the constructibility condition, we do the entire computation

above for successive values S =1, 2, 3,... approximating the true space

bound S(n). In the course of the computation for S, we eventually see all

conﬁgurations of length S reachable from the start conﬁguration, and can

24 Lecture 4

check whether M ever tries to use more than S space. If so, we know that

S is too small and can restart the computation with S +1. 2

Lecture 5

Logspace Computability

For either deterministic or nondeterministic machines, the following re-

sources are equally powerful:

(i) Logarithmic workspace;

(ii) Counting up to n, the length of the input; and

(iii) “Finite ﬁngers”.

By this we mean that the following classes of automata can simulate one

another:

(i) Logspace-bounded TMs;

(ii) Automata with a two-way read-only input head and a ﬁxed ﬁnite

number of integer counters that can hold an integer between 0 and

n, the length of the input; and

(iii) Automata with a ﬁxed ﬁnite number of two-way read-only input

heads that may not move outside the input.

A machine of type (ii) with k counters is called, appropriately enough, a

k-counter automaton with linearly bounded counters.Ineachstep,sucha

machine may test each of its counters for zero. Based on this information

26 Lecture 5

and its current state, it may add one or subtract one from each of the coun-

ters, move its read head left or right, and enter a new state. Without the

bound of n on the maximum value of the counters, a two-counter machine

could simulate an arbitrary Turing machine. But with the bound, k-counter

machines are no more powerful than logspace machines.

A machine of type (iii) with k heads is called a k-headed two-way ﬁnite

automaton (k-FA).

Intuitively, logspace is enough to simulate a ﬁnite number of integer

counters that may count only up to n, because the value of the counters can

be kept on the worktape in binary. Conversely, the values in the counters

can simulate the contents of the worktape, although this simulation is a

little more complicated; it takes a bit of cleverness to ﬁgure out how to

simulate reading and writing symbols on the worktape by manipulating

the values in the counters (Homework 1, Exercise 2).

A two-way read head can simulate a linearly bounded counter by main-

taining the count as the distance from the left endmarker; conversely, a

counter can maintain the distance of a simulated read head from the left

endmarker (Miscellaneous Exercise 9).

Logspace Transducers

A logspace transducer is a total deterministic logspace-bounded Turing ma-

chine with output. Total means it halts on all inputs. A logspace transducer

has

• a two-way read-only input tape;

• a two-way read/write logspace-bounded worktape, initially blank;

and

• a write-only left-to-right output tape, initially blank.

It has three ﬁnite alphabets Σ, Γ, and ∆, the input, worktape, and output

alphabets, respectively.

The machine begins in its start state with all the heads positioned all the

way to the left on the three tapes. The input string x ∈ Σ

∗

iswrittenonthe

input tape between endmarkers, and the input head may never go outside

the endmarkers. It runs as a normal logspace TM, reading symbols on its

input tape and reading and writing symbols on its worktape. Occasionally

it may enter a special state that causes it to write a symbol in ∆ on its

output tape and advance the output tape head one cell. When the machine

halts (which it must, by assumption), the string in ∆

∗

that is written on

the output tape at that point is the value of the function computed by the

machine on input x.