Kozen D.C. Theory of Computation

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

Contents xiii

Hints and Solutions 317

Homework1 Solutions...................................... 319

Homework2 Solutions...................................... 323

Homework3 Solutions...................................... 326

Homework4 Solutions...................................... 329

Homework5 Solutions...................................... 332

Homework6 Solutions...................................... 334

Homework7 Solutions...................................... 337

Homework8 Solutions...................................... 343

Homework9 Solutions...................................... 347

Homework10Solutions..................................... 351

Homework11Solutions..................................... 354

Homework12Solutions..................................... 357

Hints forSelected MiscellaneousExercises .................... 361

Solutionsto SelectedMiscellaneousExercises ................. 367

References 391

Notation and Abbreviations 399

Index 409

Lecture 1

The Complexity of Computations

In this course we are concerned mainly with two broad issues:

• The deﬁnition and study of various computational models and pro-

gramming constructs, with an eye toward understanding their relative

power and limitations;

• The classiﬁcation of computational problems in terms of their inher-

ent complexity. This usually means time or space complexity on a

particular model, but may include other measures as well, such as

randomness, number of alternations, or circuit size.

This area of study is generally known as computational complexity theory.

It has deep roots in the theory of computability as developed by Church,

Kleene, Post, G¨odel, Turing, and others in the ﬁrst half of the twentieth

century.

It is widely acknowledged that the genesis of the theory as we know it

today was the 1965 paper, “On the Computational Complexity of Algo-

rithms,” by Juris Hartmanis and Richard Stearns [55]. Although mathe-

maticians had previously studied the complexity of algorithms, this paper

showed that computational problems often have an inherent complexity,

which can be quantiﬁed in terms of the number of time steps needed on a

simple model of a computer, the multitape Turing machine, but is largely

4 Lecture 1

independent of the particular model of computation. In a subsequent pa-

per with Philip Lewis [115], they showed that space complexity (number

of tape cells used) can also be treated as a complexity measure in much

the same way as time. Other pioneering work on computational complexity

that appeared around the same time included papers of Cobham [30] and

Edmonds [37], who are generally credited with the invention of the notion

of polynomial time, and Hennie and Stearns [60]. Edmonds was apparently

the ﬁrst to conjecture that P = NP. These papers were immediately rec-

ognized as a fundamental advance. Indeed, it was the original Hartmanis

and Stearns paper [55] that gave the name computational complexity to the

discipline.

The fundamental contribution of Hartmanis and Stearns was not so

much the speciﬁc results regarding the complexity of Turing machine com-

putations, but the assimilation of concrete notions of resource usage into a

general theory of computational complexity. Although they worked primar-

ily with multitape Turing machines, they argued rightly that the concepts

were universal and that the same behavior would emerge in any reasonable

model. The fundamental notion of complexity class laid down in their orig-

inal paper still pervades the ﬁeld. The theory has been further generalized

by Manuel Blum [16] using an abstract notion of complexity measure, and

many results generalize to this more abstract setting (see Supplementary

Lecture J). Other resources besides time and space, from area in VLSI

layout problems to randomness in probabilistic computation, have been

successfully treated in this framework.

Today the ﬁeld also includes a wide variety of notions such as prob-

abilistic complexity classes, interactive proof systems, approximation and

inapproximation results, circuit complexity, and many others. The primary

goal of this ﬁeld is to understand what makes computational problems com-

plex, with the hope that by doing so, we might better understand how to

make them simpler.

Turing Machines

A convenient starting point for our study is Turing machine (TM) com-

plexity. Turing machines were invented in 1936 by Alan M. Turing [123]

at around the same time as several other formalisms purporting to cap-

ture the notion of eﬀective computability: Post systems [94, 95], µ-recursive

functions [47], λ-calculus [28, 71], and combinatory logic [109, 35].

All these models are computationally equivalent in the sense that they

can simulate one another. This led Alonzo Church to formulate Church’s

thesis [29, 123], which states that these models exactly capture our intu-

itive notion of eﬀective computability. But one aspect of computability that

Church’s thesis does not address is the notion of complexity. For example,

The Complexity of Computations 5

it is true that a deterministic two-counter automaton can simulate an ar-

bitrary nondeterministic multitape Turing machine, but only at great cost.

We are thus left with the task of deﬁning reasonable models in which these

complexity questions can be formulated and studied.

The Turing machine is a good, albeit imperfect, model for deﬁning basic

time and space complexity, because at least for higher levels of complexity,

the deﬁnitions are robust and reﬂect fairly accurately our expectations of

real-life computation.

The One-Tape Turing Machine: A Quick Review

We review here the deﬁnition of deterministic, one-tape Turing machines

that act as acceptors. Inputs to such a machine are ﬁnite-length strings

over some ﬁxed ﬁnite alphabet Σ. The length of a string x is denoted |x|.

We also use the same notation |A| for the size (cardinality) of a set A.The

unique string of length 0 is called the null string and is denoted ε.Theset

of all ﬁnite-length strings over Σ is denoted Σ

∗

Informally, the machine has a ﬁnite set of states Q, a semi-inﬁnite tape

that is delimited on the left end by an endmarker  and is inﬁnite to the

right, and a head that can move left and right over the tape, reading and

writing symbols from a ﬁnite alphabet Γ that contains Σ as a subset.

 abbaba ···

two-way, read/write

The input string is initially written on the tape in contiguous tape cells

snug up against the left endmarker. The inﬁnitely many cells to the right

of the input all contain a special blank symbol .

The machine starts in its start state s with its head scanning the left

endmarker. In each step it reads the symbol on the tape under its head.

Depending on that symbol and the current state, it writes a new symbol on

that tape cell, moves its head either left or right one cell, and enters a new

state. The action it takes in each situation is determined by a transition

function δ.Itaccepts its input by entering a special accept state t and

rejects by entering a special reject state r. If it either accepts or rejects

its input, then it is said to halt on that input. On some inputs it may run

inﬁnitely without ever accepting or rejecting, in which case it is said to loop

on that input. The subset of Σ

∗

consisting of all input strings accepted by

the TM M is denoted L(M).

6 Lecture 1

Formally, a deterministic one-tape Turing machine is a 9-tuple

M =(Q, Σ, Γ, , ,δ,s,t,r),

where

• Q is a ﬁnite set of states;

• Σ is a ﬁnite input alphabet;

• Γ is a ﬁnite tape alphabet containing Σ as a subset;

•  ∈ Γ −Σistheblank symbol;

•∈Γ − Σistheleft endmarker ;

• δ : Q × Γ → Q × Γ ×{L, R} is the transition function;

• s ∈ Q is the start state;

• t ∈ Q is the accept state;and

• r ∈ Q is the reject state, r = t.

Intuitively, δ(p, a)=(q, b,d) means, “When in state p scanning symbol a,

write b on that tape cell, move the head in direction d, and enter state q.”

The symbols L and R stand for left and right, respectively.

We restrict TMs so that the left endmarker is never overwritten with

another symbol and the machine never moves oﬀ the tape to the left of the

endmarker; that is, we require that for all p ∈ Q there exists q ∈ Q such

that

δ(p, )=(q,,R). (1.1)

We also require that once the machine enters its accept state, it never leaves

it, and similarly for its reject state; that is, for all b ∈ Γ there exist c, c



∈ Γ

and d, d



∈{L, R} such that

δ(t, b)=(t, c, d),δ(r, b)=(r, c



). (1.2)

We refer to the state set and transition function collectively as the ﬁnite

control.

There are many variations on Turing machines: two-way inﬁnite tapes,

multiple tapes, multiple accept and reject states, various forms of stacks

and counters. Most of these variations produce machines that are compu-

tationally equivalent in that they are all capable of accepting the same

sets. However, as mentioned, they are not necessarily equivalent from the

standpoint of resource usage.

A TM as described above is an acceptor; that is, for each input x,it

either accepts x, rejects x,orloopsonx. This amounts to computing a

The Complexity of Computations 7

partial {0, 1}-valued function. TMs can also be equipped with an output

tape and speciﬁed output alphabet ∆ to compute partial functions with

range ∆

∗

An important variation is the nondeterministic Turing machine. A de-

terministic TM, as deﬁned above, has a uniquely determined next conﬁgu-

ration from any given conﬁguration as speciﬁed by its transition function

δ. A nondeterministic machine has a ﬁxed ﬁnite choice of moves at each

transition. Formally, δ is a relation, not a function. The computation of

a deterministic machine can be described as a sequence of conﬁgurations

beginning with the start conﬁguration. A nondeterministic machine, on the

other hand, determines a tree of possible computations, the root of which

is the start conﬁguration. The children of any node are the possible con-

ﬁgurations that can be reached in one step. A nondeterministic machine

is said to accept its input if there is some path in the computation tree

leading to an accept conﬁguration.

Because a Turing machine is a ﬁnite object, it is possible to encode

it as a sequence of symbols over some alphabet in such a way that the

resulting codes can be read and interpreted by another Turing machine

and simulated. This leads to the notion of a universal Turing machine.

See [61, 76, 113] for a more complete treatment.

Crossing Sequences

Let us reacquaint ourselves with Turing machines by deriving a couple

of results from [59, 115] on Turing machine time and space usage. These

results illustrate the use of a counting technique to show lower complexity

bounds.

Theorem 1.1 Let Σ={0, 1, #}.Thesetof palindromes

PAL

def

= {z ∈ Σ

∗

| z =revz}

requires Ω(n

) time on a one-tape TM.

Here rev x denotes x written backwards. Note that this result holds

for one-tape TMs only; PAL can be accepted in linear time on a two-tape

machine.

Proof. Let M be any machine accepting PAL. Assume without loss of

generality that whenever M accepts, it ﬁrst moves to the right end of the

nonblank portion of the tape before entering its accept state. For each n

that is a multiple of 4, consider the action of M on elements of PAL of the

form

PAL

def

= {x #

n/2

rev x | x ∈{0, 1}

n/4

8 Lecture 1

All elements of PAL

are of length n and PAL

⊆ PAL. For each x ∈ PAL

and each position i,0≤ i ≤ n,letc

(x) denote the sequence q

,... ,q

of states of the ﬁnite control Q of M that M is in as it passes over the line

between the ith symbol and the i + 1st in either direction while scanning

x. This is called the crossing sequence at i.Let

C(x)

def

= {c

(x) | n/4 ≤ i ≤ 3n/4}.

Lemma 1.2 If x, y ∈ PAL

and x = y,thenC(x) ∩ C(y)=∅.

Proof. Suppose c ∈ C(x) ∩ C(y), say c = c

(x)=c

(y). Let x



be the

preﬁx of x consisting of the ﬁrst i symbols, and let y



be the suﬃx of y

consisting of the last n − j symbols. Then x



is accepted by M, because

the machine behaves to the left of c as if it were scanning x and to the

right of c as if it were scanning y; in particular, it accepts. But x



is not

in PAL, because it is not a palindrome. This is a contradiction. 2

Resume proof of Theorem 1.1.Letm

be the length of the shortest

crossing sequence in C(x). We show that some m

, x ∈ PAL

,hastobe

long. Let m =max{m

| x ∈ PAL

}.Then



i=0

|Q|

m+1

− 1

|Q|−1

≥ 2

n/4

The left hand side of the inequality gives the number of possible crossing se-

quences of length at most m. The right hand side is the number of elements

of PAL

. The inequality holds because all the shortest crossing sequences

for elements of PAL

must be diﬀerent, by Lemma 1.2. By taking logs it

follows that

m ≥ Ω(n).

Then there must be an x ∈ PAL

such that m

≥ Ω(n). Because m

is the

length of the shortest crossing sequence in C(x), all crossing sequences in

C(x)areoflength≥ Ω(n), thus it takes at least

· Ω(n)=Ω(n

)timeto

generate all the crossing sequences in C(x). 2

The next result uses the same technique to show that o(log log n)work-

space is no better than no workspace at all.

Theorem 1.3 If M runs in o(log log n) space, then M accepts a regular set.

There is a nonregular set accepted in O(log log n) space:

{#b

(0)#b

(1)#b

(2)# ···#b

− 1)# | k ≥ 0},

where b

(i) denotes the k-bit binary representation of i (Homework 2, Ex-

ercise 4).

The Complexity of Computations 9

Proof. Assume without loss of generality that M has a read-only input

tape and one read/write worktape, and that M always moves its input

head all the way to the right of the input string before accepting. If M is

S(n) space-bounded, then on inputs of length n there are at most

N = q ·S(n) · d

S(n)

(1.3)

possible conﬁgurations of state, workhead position, and worktape contents,

where q is the number of states and d is the size of the worktape alphabet

of M (the position of the input head is not counted). These data constitute

the total information that can be transferred across a vertical line drawn at

some position i in the input string as the input head passes over that line.

For this proof, the crossing sequence at i consists of the sequence of such

conﬁgurations occurring at position i in the input string in either direction.

There are



i=0

m+1

− 1

N − 1

possible crossing sequences of length at most m.

Lemma 1.4 If there is a ﬁxed ﬁnite bound k on the amount of space used by M on

accepted inputs, then L(M) is a regular set.

Proof. If M uses at most k worktape cells on all accepted inputs, we can

modify M to mark oﬀ k cells initially (k can be kept in the ﬁnite control)

and reject if the computation ever tries to use more than k cells. That way

wecanmakesurethatM uses no more than k tape cells on any input. But

then no worktape memory is needed at all; the contents of the worktape

can be kept in the ﬁnite control. Thus M is equivalent to a two-way ﬁnite

automaton. 2

Resume proof of Theorem 1.3. Suppose L(M) is not regular. By Lemma

1.4, there is no ﬁxed ﬁnite bound on the amount of worktape used on inputs

in L(M ). Thus for each k, there exists a string x ∈ L(M) of minimal length

for which at least k worktape cells are used. Here “of minimal length” means

that for all shorter strings in L(M), M uses fewer than k worktape cells.

Let n = |x| and let c be a crossing sequence containing an occurrence of a

conﬁguration using k worktape cells. If c occurs in the right half of x,then

the ﬁrst n/2 crossing sequences must all be distinct, otherwise a section

of x could be cut out to obtain a shorter string accepted with crossing

sequence c, contradicting the minimality assumption. If c occurs in the left

half, then the last n/2 crossing sequences must all be distinct for the same

reason. In either case, there are at least n/2 distinct crossing sequences.

10 Lecture 1

In order to have n/2 distinct crossing sequences, there must be a crossing

sequence of length at least m,where

≤



i=0

m+1

− 1

N − 1

. (1.4)

Moreover, no crossing sequence can be of length greater than 2N,otherwise

a conﬁguration would be repeated in the crossing sequence twice in the

same direction, thus M would be looping, contradicting the fact that x is

accepted. Thus

m ≤ 2N. (1.5)

Combining (1.3), (1.4), and (1.5) and taking logs, we get

S(n) ≥ Ω(log log n).

Lecture 2

Time and Space Complexity Classes and

Savitch’s Theorem

Let T : N → N and S : N → N be numeric functions, which serve as

asymptotic time and space bounds for Turing machine computations. These

functions are usually written as functions of a single numeric variable n

standing for the length of the input string; for example, log n,(logn)

, n,

n log n, n

(log n)

, n!, 2

,andsoon.

Deﬁnition 2.1 We say that a nondeterministic TM runs in time T (n) or is T (n)time-

bounded if on all but ﬁnitely many inputs x, no computation path takes

more than T (|x|) steps before halting, where |x| denotes the length of x.

We say that a nondeterministic TM runs in space S(n) or is S(n)

space-bounded if on all but ﬁnitely many inputs x, no computation path

uses more than S(|x|) worktape cells, where |x| is the length of x.

In Deﬁnition 2.1, the “but ﬁnitely many” is there mainly to avoid trivial

counterexamples involving the null string, but it is also often technically

convenient in asymptotic complexity to be able to ignore small inputs. We

can always store a ﬁnite amount of data in the ﬁnite control and do table

lookup for ﬁnitely many inputs.

Note that to run in a certain amount of time or space, the machine

must not exceed the stated bounds even on nonaccepting computations.

The following are the basic time and space complexity classes.