Kozen D.C. Theory of Computation

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

Logspace Computability 27

Only worktape space usage is counted in the space bound; the output

tape is not counted.

A function σ :Σ

∗

→ ∆

∗

is called logspace computable if it is computed

by some logspace transducer in this way.

The output of a logspace transducer is polynomially bounded in length.

That is, for any logspace computable function σ :Σ

∗

→ ∆

∗

,thereisa

constant d such that for all x ∈ Σ

∗

, |σ(x)|≤|x|

. This is because a

logspace transducer can emit at most one output symbol per step, and it

can run for at most polynomially many steps, because otherwise it would

repeat a conﬁguration, in which case it would be in an inﬁnite loop.

Logspace Reducibility

To encode one problem in another, we use a reducibility relation known

as logspace reducibility. This is a relation that is computed by a logspace

transducer. Logspace reducibility was ﬁrst studied by Savitch [108] and

Jones [67].

If A ⊆ Σ

∗

and B ⊆ ∆

∗

,wewriteA ≤

log

B and say A is logspace

reducible to B if there is a logspace-computable function σ :Σ

∗

→ ∆

∗

such

that for all x ∈ Σ

∗

x ∈ A ⇔ σ(x) ∈ B.

The subscript m on ≤

log

stands for “many–one” and refers to the type of

reducibility relation.

Lemma 5.1 The relation ≤

log

is transitive. That is, if A ≤

log

B and B ≤

log

C,then

A ≤

log

Proof. Homework 1, Exercise 1. This is nontrivial, because there is not

enough space to write down an intermediate result in its entirety. 2

Lemma 5.2 For A ∈ Σ

∗

, A ∈ LOGSPACE iﬀ A ≤

log

{0, 1}.

Proof. A logspace decision procedure for membership in A is essentially

a reduction of A to a two-element set. 2

Lemma 5.3 If A ≤

log

B and B ∈ LOGSPACE, then A ∈ LOGSPACE.

Proof. This follows immediately from Lemmas 5.1 and 5.2. 2

In the theory of NP-completeness, you might have studied the

polynomial-time many–one reducibility relation ≤

,alsoknownasKarp re-

ducibility. The relations ≤

and ≤

log

are similar, except that ≤

is deﬁned

28 Lecture 5

in terms of polynomial time transducers, which are the same as logspace

transducers except that the bound is on time instead of space. Because

logspace transducers can run for at most polynomial time, we have imme-

diately that

Lemma 5.4 If A ≤

log

B then A ≤

It is not known whether ≤

log

is strictly stronger than ≤

, however.

Although ≤

is adequate for studying the P = NP question, we are

interested in the stronger reducibility ≤

log

because it has consequences for

lower complexity classes such as LOGSPACE and NLOGSPACE.Most

of the natural polynomial-time reductions appearing in the literature can

actually be done in logspace.

Completeness

AsetA ∈ Σ

∗

is said to be ≤

log

-hard for a complexity class C if B ≤

log

for all B ∈ C.Intuitively,A is as hard as any decision problem in C, because

it can encode any decision problem in C.AsetA is said to be complete for

C with respect to ≤

log

(i) A is ≤

log

-hard for C,and

(ii) A ∈ C.

Sometimes we say that A is ≤

log

-complete for C or just C-complete if the

reducibility relation ≤

log

is understood. Intuitively, A is a hardest element

of C in the sense that it encodes every other element of C.

The Cook–Levin theorem says that Boolean satisﬁability is NP-

complete. The usual proofs of the Cook–Levin theorem only show ≤

completeness, but it is easily shown that the problem is complete with

respect to the stronger reducibility ≤

log

. We derive this as a corollary next

time.

Here is the canonical NLOGSPACE-complete problem that is to the

LOGSPACE = NLOGSPACE question as Boolean satisﬁability is to the

P = NP question.

Deﬁnition 5.5 The problem MAZE (also known as directed graph reachability)isthe

problem of determining, given a directed graph G =(V, E) and distinguished

vertices s, t ∈ V , whether there exists a directed path from s to t.

Theorem 5.6 (Jones, Lien, and Laaser [68]) MAZE is ≤

log

-complete for NLOGSPACE.

Proof. We must show

(i) MAZE is ≤

log

-hard for NLOGSPACE,and

Logspace Computability 29

(ii) MAZE ∈ NLOGSPACE.

Part (ii) is easy, because we can trace our way through the given graph using

ﬁnitely many ﬁngers, guessing the path from s to t nondeterministically.

To show (i), let A be an arbitrary element of NLOGSPACE .Wemust

show that A ≤

log

MAZE. Suppose M is a nondeterministic logspace-

bounded TM accepting A.Letstart and accept be the start and accept

conﬁgurations of M, respectively. We can assume without loss of generality

that accept is unique by making M erase its worktape and move its heads

all the way to the left before accepting. We build a graph G =(V, E), where

V is a ﬁnite set of conﬁgurations of M containing all conﬁgurations of M

on input x,andE is the next-conﬁguration relation on input x.ThenM

accepts x iﬀ there is a path from start to accept in G.

Recall that a conﬁguration of M consists of the current state, the cur-

rent head positions, and the current contents of the worktape. For an input

x of length n, all this information takes only log n space to record, say as

astringoflengthlogn over an alphabet ∆ of size d. We can thus take

V =∆

log n

. This set is of size d

log n

= n

log d

. We take the edges E to be the

pairs (α, β) such that α and β are encodings of conﬁgurations of M and β

follows from α in one step on input x according to the transition rules of

It remains to argue that this graph can be produced by a logspace

transducer on input x. The transducer ﬁrst outputs the set of vertices

∆

log n

. This is easy: it lays oﬀ log n space on its worktape, then cycles

through all strings in ∆

log n

lexicographically, outputting them all. For the

edges, it writes down all pairs α, β in lexicographic order. For each pair,

it checks that they both encode conﬁgurations of M and that α goes to

β in one step on input x. It has to read the ith symbol of its input x to

determine this, where i is the position of the input head speciﬁed by α.If

so, it outputs the edge (α, β). Finally, it outputs the two strings encoding

the conﬁgurations start and accept.

Although the output (V,E, start, accept) is polynomial in length, only

logarithmic workspace was used to produce it, because there were only at

most two conﬁgurations of M written down on the transducer’s worktape

at any time. Thus the map x → (V,E,start, accept) is computable in

logspace and constitutes a reduction from A to MAZE. 2

Corollary 5.7 MAZE ∈ LOGSPACE iﬀ LOGSPACE = NLOGSPACE.

Proof. Lemmas 5.1 and 5.2 and Theorem 5.6. 2

Omer Reingold [101] has very recently shown that the undirected graph

reachability problem is solvable in deterministic LOGSPACE .

Lecture 6

The Circuit Value Problem

In the early 1970s, Stephen Cook [31] and independently Leonid Levin [79]

showed that the Boolean satisﬁability problem (SAT)—whether a given

Boolean formula has a satisfying truth assignment—is NP-complete. Thus

Boolean satisﬁability is in P iﬀ P = NP . This theorem has become known

as the Cook–Levin theorem. Around the same time, Richard Karp [70]

showed that a large number of optimization problems in the ﬁeld of oper-

ations research such as the traveling salesperson problem, graph coloring,

bin packing, and many others were all interreducible and therefore NP-

complete. These two milestones established the study of NP-completeness

as an important aspect of theoretical computer science. In fact, the question

of whether P = NP is today widely considered one of the most important

open questions in all of mathematics.

There is a theorem of Ladner [78] that plays the same role for the P =

NLOGSPACE or P = LOGSPACE question that the Cook–Levin theorem

plays for the P = NP question. The decision problem involved is the circuit

value problem (CVP): given an acyclic Boolean circuit with several inputs

and one output and a truth assignment to the inputs, what is the value of

the output? The circuit can be evaluated in deterministic polynomial time;

the theorem says that this problem is ≤

log

-complete for P. It follows from

the transitivity of ≤

log

that P = NLOGSPACE iﬀ CVP ∈ NLOGSPACE

and P = LOGSPACE iﬀ CVP ∈ LOGSPACE.

The Circuit Value Problem 31

Formally, a Boolean circuit is a program consisting of ﬁnitely many

assignments of the form

:= 0,

:= 1,

:= P

∧ P

,j,k<i,

:= P

∨ P

,j,k<i,or

:= ¬P

,j<i,

where each P

in the program appears on the left-hand side of exactly one

assignment. The conditions j, k < i and j<iensure acyclicity. We want

to compute the value of P

,wheren is the maximum index.

Theorem 6.1 The circuit value problem is ≤

log

-complete for P.

Proof. We have already argued that CVP ∈ P . To show hardness, we

reduce an arbitrary A ∈ P to CVP. Let M be a deterministic single-tape

polynomial-time-bounded TM accepting A, say with time bound n

.LetΓ

be the worktape alphabet of M and let Q be the set of states of M’s ﬁnite

control. The transition function δ of M is of type δ : Q×Γ → Q×Γ×{L, R}.

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

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

can encode conﬁgurations of M over a ﬁnite alphabet ∆ as usual.

Now given x of length n, think of the successive conﬁgurations of M on

input x as arranged in an (n

+1)×(n

+1) time/space matrix R with entries

in ∆. The ith row of R is a string in ∆

describing the conﬁguration of

the machine at time i.Thejth column of R describes what is going on at

tape cell j throughout the history of the computation.

For example, the ith row of the matrix might look like

 a b a a b

b a a b a b   

and the i + 1st might look like

 a b a a b b

a a b a b   

This would happen if δ(p, a)=(q, b,R). The elements of ∆ are thus of the

form

32 Lecture 6

for a ∈ Γandq ∈ Q.

We can specify the matrix R in terms of a set of local consistency condi-

tions on (n

+1)×(n

+1) matrices over ∆. Each local consistency condition

is a relation on the entries of the matrix in a small neighborhood of some

location i, j. The conjunction of all these local consistency conditions is

enough to determine R uniquely.

Our circuit will involve Boolean variables

, 0 ≤ i, j ≤ n

,a∈ Γ,

, 0 ≤ i, j ≤ n

,q∈ Q.

The variable P

says, “The symbol occupying tape cell j at time i is a,”

and the variable Q

says, “The machine is in state q scanning tape cell j

at time i.”

Now we write down a set of conditions in terms of the P

and Q

describing all ways that the machine could be in state q scanning tape cell

j at time i or that the symbol occupying tape cell j at time i is a.

For 1 ≤ i ≤ n

,0≤ j ≤ n

,andb ∈ Γ, we include the assignment



δ(p,a)=(q,b,d)

i−1,j

∧P

i−1,j

) (6.1)

∨ (P

i−1,j

∧



p∈Q

¬Q

i−1,j

) (6.2)

in our circuit. Intuitively, this says, “The symbol occupying tape cell j at

time i is b if and only if either the machine was scanning tape cell j at time

i − 1 and printed b (clause (6.1)), or the machine was not scanning tape

cell j at time i − 1 and the symbol occupying that cell at time i −1wasb

(clause (6.2)).” The join in (6.1) is over all states p, q ∈ Q,symbolsa ∈ Γ,

and directions d ∈{L, R} such that δ(p, a)=(q, b,d); that is, all situations

that would cause b to be printed.

For 1 ≤ i ≤ n

,1≤ j ≤ n

− 1 (that is, ignoring the left and right

boundaries), and q ∈ Q, we include the assignment



δ(p,a)=(q,b,R)

i−1,j−1

∧ P

i−1,j−1

) (6.3)

∨



δ(p,a)=(q,b,L)

i−1,j+1

∧ P

i−1,j+1

). (6.4)

Intuitively, this says, “The machine is scanning tape cell j at time i if and

only if either it was scanning tape cell j −1 at time i −1andmovedright

(clause (6.3)), or it was scanning tape cell j +1 attime i − 1andmoved

left (clause (6.4)).” The join in (6.3) is over all states p ∈ Q and symbols

The Circuit Value Problem 33

a, b ∈ Γ such that δ(p, a)=(q, b, R); that is, all situations that would cause

the machine to move right and enter state q.

For j = 0, that is, for the leftmost tape cell, we deﬁne Q

in terms of

(6.3) only. Similarly, for j = n

, we deﬁne Q

in terms of (6.4) only.

This takes care of everything except the ﬁrst row of the matrix. The

values P

and Q

are determined by the start conﬁguration; these are the

inputs to the circuit. If x = a

···a

, the start state is s, and the endmarker

and blank symbol are  and , respectively, we include



0,0

:= 1,

0,0

:= 0,b∈ Γ −{},

0,j

:= 1, 1 ≤ j ≤ n,

0,j

:= 0,b∈ Γ −{a

}, 1 ≤ j ≤ n,



0,j

:= 1,n+1≤ j ≤ n

0,j

:= 0,b∈ Γ −{},n+1≤ j ≤ n

0,0

:= 1,

0,j

:= 0, 1 ≤ j ≤ n

0,j

:= 0, 0 ≤ j ≤ n

,q ∈ Q −{s}.

This gives a circuit. Assuming that the machine moves its head all the

way to the left before entering its accept state t, the Boolean value of

∨ Q

determines whether M accepts x.

The construction we have just given can be done in logspace. Even

though the circuit is polynomial size, it is highly uniform in the sense that

it is built of many identical pieces. The only diﬀerences are the indices i, j,

whichcanbewrittendowninlogspace. 2

The Cook–Levin Theorem

Now we show how to derive the Cook–Levin theorem as a corollary of the

previous construction. We would like to show that the Boolean satisﬁability

problem SAT—given a Boolean formula, does it have a satisfying truth

assignment?—is NP-complete. The two main diﬀerences between SAT and

CVP are:

(i) With SAT, the input values are not provided. The problem asks

whether there exist values making the formula evaluate to true.

34 Lecture 6

(ii) CVP is deﬁned in terms of circuits and SAT is deﬁned in terms of

formulas. The diﬀerence is that in circuits, Boolean values may be

used more than once. A circuit is represented as a labeled directed

acyclic graph (dag), whereas a formula is a labeled tree. Another way

to look at it is that a circuit allows sharing of common subexpressions.

The satisﬁability problem is NP-complete, regardless of whether we

use circuits or formulas; but the problem of evaluating a formula on

a given truth assignment is apparently easier than CVP, because it

can be done in logspace (Homework 2, Exercise 3).

We deﬁne a circuit with unspeciﬁed inputs exactly as above, except that

we also include assignments

:= ?

denoting inputs whose value is unspeciﬁed.

Theorem 6.2 Boolean satisﬁability is ≤

log

-complete for NP.

Proof. Boolean satisﬁability is in NP, because we can guess a truth

assignment and verify that it satisﬁes the given formula or circuit in poly-

nomial time.

To show that the problem is ≤

log

-hard for NP,letA be an arbitrary set

in NP, and let M be a nondeterministic machine accepting A and running

in time n

. Assume without loss of generality that the nondeterminism is

binary branching. Then a computation path of M is speciﬁed by a string

in {0, 1}

Let M



be a deterministic machine that takes as input x#y,where

|y | = |x|

, and runs M on input x,usingy to resolve the nondeterministic

choices and accepting if the computation path of M speciﬁed by y leads

to acceptance. By the construction of Theorem 6.1, there is a circuit that

has value 1 iﬀ M



accepts x#y. Note from the construction that if |z | =

|y | = n

, the circuit constructed for x#z is identical to that for x#y

except for the inputs corresponding to y; making these inputs unspeciﬁed,

we obtain a circuit C(P

,... ,P

) with unspeciﬁed inputs P

,... ,P

such

that M accepts x if and only if there exist y

,... ,y

∈{0, 1} such that

C(y

,... ,y

)=1.

We can transform the circuit into a formula by replacing each assign-

ment P

:= E with the clause P

↔ E and taking the conjunction of all

clauses obtained in this way. The resulting formula is satisﬁable iﬀ M ac-

cepts x. 2

The Boolean satisﬁability problem remains NP-hardevenwhenre-

stricted to formulas in conjunctive normal form (CNF with at most three

literals per clause (3CNF) (Miscellaneous Exercise 10), whereas it is solv-

able in polynomial time for formulas in 2CNF (Homework 2, Exercise 2).

The satisﬁability problem for 3CNF formulas is known as 3SAT.

Supplementary Lecture A

The Knaster–Tarski Theorem

Transﬁnite Ordinals

Everyone is familiar with the set ω = {0, 1, 2,...} of ﬁnite ordinals,also

known as the natural numbers.Anessentialmathematicaltoolisthein-

duction principle on this set, which states that if a property is true of zero

and is preserved by the successor operation, then it is true of all elements

of ω.

In theoretical computer science, we often run into inductive deﬁnitions

that take longer than ω to close, and it is useful to have an induction prin-

ciple that applies to these objects. Cantor recognized the value of such a

principle in his theory of inﬁnite sets. Any modern account of the foun-

dations of mathematics will include a chapter on ordinals and transﬁnite

induction.

Unfortunately, a complete understanding of ordinals and transﬁnite in-

duction is impossible outside the context of set theory, because many issues

impact the very foundations of the subject. Here we only give a cursory

account of the basic facts, tools, and techniques we need.

36 Supplementary Lecture A

Set-Theoretic Deﬁnition of Ordinals

Ordinals are deﬁned as certain sets of sets. The key facts we need about

ordinals, succinctly stated, are:

(i) There are two kinds: successors and limits.

(ii) They are well ordered.

(iii) There are a lot of them.

(iv) We can do induction on them.

We explain each of these statements in more detail below.

AsetC of sets is said to be transitive if A ∈ C whenever A ∈ B and

B ∈ C.Equivalently,C is transitive if every element of C is a subset of C;

that is, C ⊆ 2

. Formally, an ordinal is deﬁned to be a set A such that

• A is transitive; and

• all elements of A are transitive.

It follows that any element of an ordinal is an ordinal. We use α,β,γ,...

to refer to ordinals. The class of all ordinals is denoted Ord. It is not a set,

but a proper class.

This neat but rather obscure deﬁnition of ordinals has some far-reaching

consequences that are not at all obvious. For ordinals α, β, deﬁne α<β

if α ∈ β.Therelation< is a strict partial order. As usual, there is an

associated nonstrict partial order ≤ deﬁned by α ≤ β if α ∈ β or α = β.

It follows from the axioms of set theory that the relation < on ordinals

is a linear order. That is, if α and β are any two ordinals, then either

α<β, α = β,orα>β. This is most easily proved by induction on the

well-founded relation

(α, β) ≤ (α



,β



)

def

⇐⇒ α ≤ α



and β ≤ β



Then every ordinal is equal to the set of all smaller ordinals (in the sense

of <). The class of ordinals is well-founded in the sense that any nonempty

set of ordinals has a least element.

If α is an ordinal, then so is α ∪{α}. The latter is called the successor

of α and is denoted α + 1. Also, if A is any set of ordinals, then



A is an

ordinal, and is the supremum of the ordinals in A under the relation ≤.

The smallest few ordinals are

def

= ∅

def

= {0} = {∅}

def

= {0, 1} = {∅, {∅}}

def

= {0, 1, 2} = {∅, {∅}, {∅, {∅}}}