Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms

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

188 13 Further Topics From Classical Complexity Theory

Theorem 13.2.5. If s(n) can be computed in time 2

O(log n+s(n))

, then nonde-

terministic Turing machines with space bound s(n) can be simulated by deter-

ministic Turing machines using time and space both bounded by 2

O(log n+s(n))

Proof. Let L ∈ NTAPE(s(n)) and let M be the corresponding nondeterministic

Turing machine. The conﬁguration graph of M has a vertex for each of the

O(log n+s(n))

conﬁgurations. An edge goes from one conﬁguration to another if

the second is a possible successor conﬁguration of the ﬁrst for M. Using depth-

ﬁrst search we can check in linear time (with respect to the size 2

O(log n+s(n))

)

whether an accepting conﬁguration is reachable from the initial conﬁguration.



In particular,

NTAPE(log n) ⊆ P.

We conclude this section with a comparison of the polynomial hierarchy

and

PSPACE.

Theorem 13.2.6. For al l k ∈ N, Σ

⊆ PSPACE, thus PH ⊆ PSPACE.

Proof. We prove by induction on k that Σ

and Π

aresubsetsofPSPACE.

= Π

= P ⊆ PSPACE, since it is not possible in polynomial time to use

more than polynomial space. If L ∈ Σ

= NP(Π

k−1

), then by the logical

characterization of Σ

there is a decision problem L



∈ Π

k−1

and a polynomial

p such that

L =



x |∃y ∈{0, 1}

p(|x|)

:(x, y) ∈ L





Now we try all values of y in lexicographical order. The storage of the current

y requires only polynomial space p(|x|), and by the inductive hypothesis,

checking whether (x, y) ∈ L



can be done in space that is polynomial in |x| +

p(|x|). So the space required for the entire algorithm is polynomially bounded

in |x|.ThisprovesthatΣ

⊆ PSPACE; Π

⊆ PSPACE follows analogously. 

In summary, for all k ≥ 1,

DTAPE(log n) ⊆ NTAPE(log n) ⊆ P ⊆ NP ⊆ Σ

⊆ PSPACE ⊆ NPSPAC E .

13.3 PSPACE-complete Problems

By Deﬁnition 5.1.1, a decision problem L is PSPACE-complete if it belongs to

PSPACE and every decision problem L



∈ PSPACE can by polynomially reduced

to L,thatis,L



≤

L.JustasNP-complete problems can be solvable in

nondeterministic linear time, so

PSPACE-complete problems don’t necessarily

require a lot of space. But since Σ

⊆ PSPACE (Theorem 13.2.6) and Σ

is closed under polynomial reductions, a PSPACE-complete problem can only

be in Σ

if Σ

= PSPACE.SoforPSPACE-complete problems it is “even less

likely” than for

NP-complete problems that they can be solved in polynomial

time. Just as the generalization

Sat

cir

of Sat was the ﬁrst problem that we

showed to be Σ

-complete, so it will be another obvious generalization of these

problems that will be our ﬁrst

PSPACE-complete problem.

13.3 PSPACE-complete Problems 189

Deﬁnition 13.3.1. A quantiﬁed Boolean formula consists of a Boolean ex-

pression E(x) over 0, 1,x

,...,x

and the Boolean operators ∧ (AND), +

(OR), and ¬ (NOT), such that all the variables are quantiﬁed:

) ...(Q

): E(x) with Q

∈{∃, ∀} .

The decision problem

QBF is the decision problem of determining whether a

quantiﬁed Boolean expression is true.

In an instance of

QBF the number of quantiﬁer alternations is bounded only

by the number of variables (minus 1). So

QBF is a natural generalization of

Sat

cir

Theorem 13.3.2.

QBF is PSPACE-complete.

Proof. First we note that

QBF ∈ DTAPE(n) ⊆ PSPACE,wheren is the length

of the input. Let k be the number of quantiﬁers (which equals the number

of variables). It is easy to check whether a Boolean expression over constants

is true in linear space. This is the claim when k = 0. In the general case we

must consider both possible values of x

and for each evaluate a quantiﬁed

Boolean expression with k − 1 quantiﬁers. To store the result of one of these

evaluations while we compute the other requires only a constant amount of

extra space, so by Remark 13.2.2,

QBF ∈ DTAPE(n) ⊆ PSPACE.

Now we must show how to polynomially reduce an arbitrary problem

L ∈

PSPACE to QBF. By the results in Section 13.2 we can assume that

L is decided by a Turing machine M in space p(n)andtime2

p(n)

for some

polynomial p. As in the proof of Cook’s Theorem (Theorem 5.4.3) we will rep-

resent the computation of M with a Boolean formula. We already know that

we can express conﬁgurations using variables in space p(n) and how to test

a Boolean formula to see if the variables represent a possible conﬁguration.

We will use the abbreviated notation ∃K and ∀K for quantiﬁcation over all

the variables that represent conﬁgurations, and always assume that the test

whether the variables describe a conﬁguration is conjunctively added to the

formulas described below. The formula S(K, x) tests whether K is the initial

conﬁguration for input x,andA(K) tests whether K is an accepting conﬁgu-

ration. Finally, T

(K, K



) tests for two conﬁgurations K and K



whether K



can be reached in 2

steps from K.

Our ﬁrst attempt to transform the input x for the decision problem L into

a quantiﬁed Boolean formula Q(x)is

Q(x):=∃K

∃K

:(T

p(n)

) ∧ S(K

,x) ∧ A(K

)) .

It is clear that x ∈ L if and only if Q(x) is true, but T

p(n)

) is not yet

in the proper syntactical form. Now we describe how to bring T

)into

the proper form. For j = 0 we can reuse the construction from the proof of

Cook’s Theorem. By induction, the representation

190 13 Further Topics From Classical Complexity Theory

)=∃K :(T

j−1

,K) ∧ T

j−1

(K, K

))

is correct. Proceeding this way leads in the end to a syntactically correct but

exponentially long representation, so this cannot be done in polynomial time.

The key idea of this proof is to have T

get by with one call to T

j−1

instead

of two, as is needed in the formula above. We claim that T

)canbe

represented as

∃K

∀K

: B(K

,...,K

)+T

j−1

) (13.1)

with

B(K

,...,K

):=¬



((K

)=(K

)) + ((K

)=(K

))



In case T

)istrue,letK

be the conﬁguration reached from conﬁg-

uration K

after 2

j−1

steps. Then B(K

,...,K

) is clearly true for all pairs

except for (K

)and(K

). But the entire expression is also true for

these pairs since T

j−1

)andT

j−1

) are true. On the other hand,

if K

witnesses that Formula (13.1) is true, then it follows that T

j−1

)

and T

j−1

) and thus T

) are true. This formula can be applied

to express T

p(n)

) in terms of a T

-expression. For this we quantify over

3·p(n) conﬁgurations and there are p(n) expressions of the form B(K

,...,K

)

and then ﬁnally a T

-expression. Since conﬁgurations can be described with

polynomially many variables and can be checked for syntactic correctness with

formulas of polynomial length, and since a test for the equality of two conﬁg-

urations only requires formulas of polynomial length, the entire formula Q(x)

has polynomial length. Its simple structure makes it possible to construct

Q(x) in polynomial time. This polynomial reduction of L to

QBF proves the

theorem. 

There is a long list of

PSPACE-complete problems (see, for example, Garey

and Johnson (1979)). Interestingly many well-known games are

PSPACE-

complete, if they are generalized to arbitrary sizes. For the well-known board

games go and checkers, there are obvious generalizations to boards of size

n × n. Such generalizations for games like chess, however, seem somewhat ar-

tiﬁcial. In any case, for these generalized games we have the following decision

problem: given a legal placement of the game pieces and a player, does this

player have a winning strategy? If it is Alice’s turn to move, and her opponent

is Bob, then this question can be expressed as

∃ move for Alice ∀ move for Bob ∃ ... : Alice wins.

This representation has a certain similarity to quantiﬁed Boolean expressions.

We will not present any proofs that particular generalized games lead to

PSPACE-complete problems here. The fact that these problems are PSPACE-

complete perhaps helps explain why for the usual sizes of boards it has not

yet been possible to determine which player has a winning strategy.

13.4 Nondeterminism and Determinism in the Context of Bounded Space 191

Because of the padding technique used in the proof, we want to show that

the word problem for context-sensitive grammars

WCSL is PSPACE-complete.

For

WCSL an instance consists of a context-sensitive grammar G and a word

w. The question is whether w can be generated by G.

Theorem 13.3.3.

WCSL is PSPACE-complete.

Proof. Let (G, w) be an instance of

WCSL. The remarks before Theorem 13.2.3

show that

WCSL ∈ NTAPE(n). In Section 13.4 we will show that NTAPE(n) ⊆

DTAPE(n

). Thus WCSL ∈ PSPACE.

Now suppose L ∈

PSPACE,andletM be a deterministic Turing machine

that decides L in polynomial time using space bounded by p(n) ≥ n.FromL

we construct a decision problem

Long(L). For some special symbol Z that has

not yet been used,

Long(L)containsallstringsxZ

p(|x|)−|x|

with x ∈ L.That

is, to each word x ∈ L we add p(|x|)−|x| copies of the symbol Z. The length of

this new word is then p(|x|). We can choose p to be of such a simple form that

checking whether the input has the right number of special symbols at the end

canbedoneinp(|x|) space. After that, all we need to do is decide whether

x ∈ L. By assumption, this is possible using p(|x|) space. Because of the

artiﬁcial lengthening of the instances, it follows that

Long(L) ∈ DTAPE(n).

So by Theorem 13.2.3,

Long(L) is a context-sensitive language. The proof of

Theorem 13.2.3 is constructive and shows how a context-sensitive grammar

G(L)for

Long(L) can be constructed from the corresponding linear space-

bounded Turing machine M . Since the length of the description of M only

depends on L and p and not on the input x, the time needed to compute G(L)

is a constant with respect to |x|.Sofromx we can compute G(L)andthe

word w = xZ

p(|x|)−|x|

in polynomial time. By construction x belongs to L if

and only if w can be generated by G(L). 

13.4 Nondeterminism and Determinism in the Context

of Bounded Space

To simulate nondeterministic computations deterministically we simulate all

of the exponentially many computation paths. This requires exponential com-

putation time. But in terms of space use, we “only” need to keep track of

which paths have already been simulated. That this doesn’t require exponen-

tial space is not really very surprising.

Before we formulate this result, we want to point out a technical detail.

Here and in Section 13.5, for a space bound s(n) we want to be able to reserve

a portion of the tape with s(n) cells. This should be possible with s(n)space

available. Nevertheless, although this is possible for many important functions

s(n), it is not possible for all of them. So we will use the following deﬁnition

to separate out the “good” space bounds.

192 13 Further Topics From Classical Complexity Theory

Deﬁnition 13.4.1. A function s : N → N is called space constructible if

there is an s(n)-space-bounded deterministic Turing machine which for any

input x computes the binary representation of s(|x|).

If we have s(|x|) in binary representation, then we can mark a storage

region of length s(|x|)inspaces(|x|).

Theorem 13.4.2 (Savitch’s Theorem). If the function s(n) ≥ log n is

space constructible, then

NTAPE(s(n)) ⊆ DTAPE(s(n)

Proof. Let L be a decision problem in

NTAPE(s(n)), and let M be a nondeter-

ministic Turing machine that decides L in space s(n). We will build a Turing

machine M



that decides L deterministically in space O(s(n)

). The theorem

then follows by Remark 13.2.2.

On input x, the Turing machine M



ﬁrst computes the binary represen-

tation of s(|x|) and always describes conﬁgurations of M as conﬁgurations

with s(|x|) tape cells. This is possible because s is space constructible. By

Remark 13.2.4 and the assumption that s(n) ≥ log n, we can assume that

M runs in s(n)spaceand2

c·s(n)

time for some constant c ∈ N. Later we

will describe how we can deterministically check using O((j +1)s(n)) space

whether M can get from conﬁguration K

to conﬁguration K

in 2

steps.

The claim follows by applying this to the initial conﬁguration K

(x), the ac-

cepting conﬁguration K

,andj = c · s(n). For this we assume that there is

only one accepting conﬁguration. This is easily achieved by having the Turing

machine erase the tape (formally by writing blank symbols in each cell) and

moving the tape head to tape cell 1 before accepting.

For j = 0 the claim is simple, since we can generate from K

all possible

successor conﬁgurations and compare them with K

. For the inductive step

we apply the predicate T

) from Section 13.3, which is true if K

can

bereachedin2

steps from K

.Then

)=∃K

:(T

j−1

) ∧ T

j−1

)) .

We use extra space only to store j and to try out all K

in lexicographical

order. So we need space for two conﬁgurations and for j. The conﬁgurations

and K

are given. For each K

we use O(j · s(n)) space to check whether

j−1

) is true. In the negative case we generate the lexicographic suc-

cessor of K

and work with it. In the positive case we use the same space to

check whether T

j−1

) is true. If not, then we proceed as above; and if so,

then T

) is true. If all K

are tested without success, then T

)

is not true. Together for the test of T

we require space for the test of T

j−1

and extra space O(s(n)). So the total space required is O((j +1)· s(n)) and

the theorem is proved. 

Corollary 13.4.3.

PSPACE = NPSPACE. 

13.5 Nondeterminism and Complementation with Precise Space Bounds 193

Thus with respect to the resource of space, the analogous hierarchy to the

polynomial hierarchy collapses to the lowest level, namely to

PSPACE.

13.5 Nondeterminism and Complementation with

Precise Space Bounds

The results from Section 13.4 can be interpreted to say that to simulate non-

determinism deterministically, a bit more space suﬃces, but we believe that

for some tasks we need much more time. So it makes sense to investigate

complexity classes for ﬁxed space bounds s(n). Starting with the complexity

classes

DTAPE(s(n)), NTAPE(s(n)), and co-NTAPE(s(n)), and working analo-

gously to the polynomial hierarchy we can deﬁne a sequence of space-bounded

complexity classes. While we suspect that each class in the polynomial hier-

archy is distinct, this is not that case for these space-bounded complexity

classes even for a ﬁxed space bound. We show that for “nice” functions with

s(n) ≥ log n,

NTAPE(s(n)) = co-NTAPE(s(n)), and so the “hierarchy” that

we had imagined collapses to the ﬁrst level. The question of whether in fact

DTAPE(s(n)) = NTAPE(s(n)) has not yet been answered. For the special case

that s(n)=n this is the LBA problem (linear bounded automaton problem),

namely the question of whether the word problem for context-sensitive gram-

mars can be solved deterministically in linear space. In order to prove the

theorem mentioned above, we need to “eﬃciently” simulate a nondeterminis-

tic algorithm co-nondeterministically. The eﬃciency required, however, is only

in terms of space and not in terms of time.

Theorem 13.5.1 (Immerman und Szelepcs´enyi). If the function s(n) is

space constructible and s(n) ≥ log n, then

NTAPE(s(n)) = co-NTAPE(s(n)) .

Proof. It suﬃces to show that

NTAPE(s(n)) ⊆ co-NTAPE(s(n)) since then

co-NTAPE(s(n)) ⊆ co-co-NTAPE(s(n)) = NTAPE(s(n)) follows immediately.

So let L be a language in

NTAPE(s(n)), and let M be a nondetermin-

istic Turing machine that decides L in space s(n). Because of the space-

constructibility of s(n) ≥ log n and Remark 13.2.4, we can assume that on

every computation path M stops after at most 2

c·s(n)

computation steps for

some constant c ∈ N. If we could simulate every computation path determin-

istically in space s(n), then we could improve Savitch’s Theorem and solve

the LBA problem.

Before we explain the proof idea we want to treat a few technical details.

For an input x of length n, conﬁgurations of M will always be described for

s(n) space. Because s(n) is space-constructible, we can mark oﬀ the corre-

sponding regions on the tape. We will use counters that can take on values

from {0,...,2

c·s(n)

}. Each counter can be stored in c · s(n) + 1 tape cells.

194 13 Further Topics From Classical Complexity Theory

So as long as we store no more than constantly many counters and conﬁgu-

rations at one time, the required space will be bounded by O(s(n)) and by

Remark 13.2.2, this is equivalent to space bounded by s(n).

In order to prove that L ∈

co-NTAPE(s(n)) we must reject inputs x ∈ L

on every computation path and we must accept inputs x/∈ L on at least one

computation path. On some paths the nondeterministic algorithm M



for

will be certain that x ∈ L and halt with the answer “x ∈ L”. For

L,“x ∈ L”is

equivalent to rejecting. On some paths M



will not be certain whether x ∈ L

or x/∈ L. Since we must make the correct decision for all x ∈ L, algorithm



will halt with the conclusion “x ∈ L” on these paths. This will guarantee

a correct decision whenever x ∈ L.Furthermore,M



must guarantee for any

x/∈ L there is at least one path on which one can be sure that x/∈ L.

When can we be sure that x/∈ L? Only if we know that none of the

conﬁgurations that can be reached from the initial conﬁguration K

(x)forx

are accepting. Suppose we know the number of conﬁgurations A(x)thatcan

be reached from K

(x). Then we could proceed as follows. We step through the

conﬁgurations of M in lexicographic order. To do this we only need to store

the current conﬁguration K. Then we check nondeterministically whether it

is possible to get from K

(x)toK in 2

c·s(n)

steps. This requires space for

a counter and two conﬁgurations that contain the amount of computation

time already used, the conﬁguration reached K



, and a nondeterministically

generated conﬁguration K



.IfK



is not an immediate successor of K



,then

we halt with the output “x ∈ L”. Now consider the case that the conﬁguration



is an immediate successor of K



.IfK



= K, then we continue the process

with K



:= K



and a new nondeterministically generated K



. If we ﬁnd a

reachable accepting conﬁguration, then we stop with “x ∈ L”. This process

will stop after at most 2

c·s(n)

steps. We use another counter that starts with

the value 1 for the initial conﬁguration. For each other conﬁguration K that

we identify as reachable but not accepting, we increase the counter by one.

If we have tried out all possible conﬁgurations K and haven’t stopped, then

we compare the conﬁguration counter z with A(x). In any case z ≤ A(x). If

z<A(x), then we have failed to classify at least one reachable conﬁguration

as reachable with our nondeterministic algorithm. So our attempt to identify

all reachable conﬁgurations has failed and we halt and output “x ∈ L”. On

the other hand, if z = A(x), we have identiﬁed all reachable conﬁgurations

and determined that none of them are accepting. In this case we are certain

that x/∈ L and we can output this result. For every reachable conﬁguration

there is a sequence of conﬁgurations of the length considered describing the

corresponding computation. So for x/∈ L there is at least one computation

path in the nondeterministic algorithm just described that leads to the result

“x/∈ L”.

We have proved the theorem if we can show that A(x) can be calculated

nondeterministically. The nondeterministic computation of a number means

that computation paths can be unsuccessfully terminated, that no path can

13.6 Complexity Classes Within P 195

provide an incorrect answer, and that at least one path must provide the

correct answer.

The new idea in this proof is the nondeterministic computation of A(x).

The method used is called inductive counting because we inductively compute

(x)(for0≤ t ≤ 2

c·s(n)

), the number of conﬁgurations that are reachable

from K

(x)inatmostt steps. Clearly A

(x) = 1 since we have only the ini-

tial conﬁguration. Now suppose we know A

(x) and need to compute A

t+1

(x).

We consider all conﬁgurations K in lexicographic order and count those that

are reachable in t + 1 steps. For each K and the correct value of A

(x), we

check each conﬁguration K



as described above to determine whether it can

be reached in t steps. Conﬁguration K is reachable in at most t + 1 steps if

and only if it is one of the conﬁgurations reachable in at most t steps or an

immediate successor of one of these conﬁgurations. All attempts that do not

correctly identify all A

(x) conﬁgurations that are reachable in at most t steps

are terminated unsuccessfully. In this way we never output an incorrect an-

swer. But there must be a computation path along which each time all A

(x)

conﬁgurations that can be reached in at most t steps are correctly identiﬁed.

Along such paths it is correctly decided for each conﬁguration K whether

K can be reached in at most t + 1 steps. In this case A

t+1

(x)iscorrectly

computed. Together we have the desired nondeterministic algorithm for com-

puting A(x) and so a nondeterministic algorithm for

L. The space constraints

are not exceeded because we never need to store more than constantly many

counters and conﬁgurations. 

13.6 Complexity Classes Within P

By Theorem 13.2.5 DTAPE(log n) ⊆ NTAPE(log n) ⊆ P. We are interested

now in problems that are in

P or in NTAPE(log n) but presumably not in

DTAPE(log n). It is not immediately clear why we should be interested in such

problems since practically speaking linear space is always available without

any diﬃculty. The reason for our interest is the so-called parallel computation

hypothesis which says that small space – in particular, logarithmic space – is

closely related to polylogarithmic time on computers with polynomially many

processors. This unexpected relationship will be considered in more detail in

Chapter 14. Problems that are in

P but presumably not in DTAPE(log n)are

eﬃciently solvable but presumably do not “parallelize” well.

The investigation of the relationship between

DTAPE(log n)and

NTAPE(log n) leads to an analogue of the NP = P-problem. This analogy be-

comes our guiding principle. We can’t separate these classes, so we look for

their most diﬃcult problems. By the remarks at the beginning of Chapter 10,

we can’t do this in terms of polynomial – more precisely polynomial time –

reductions. Within

P it only makes sense to consider more restricted forms of

reductions. When investigating

P and NP we allowed polynomial algorithms.

So for an investigation of the relationship between

P and DTAPE(log n), also

196 13 Further Topics From Classical Complexity Theory

called LOGSPACE, the obvious thing to consider is algorithms that require only

logarithmically bounded space. According to our current deﬁnitions, however,

if we only allow logarithmic space, then our reductions can only compute

outputs with lengths that are logarithmically bounded in the length of the

input. This is not suﬃcient for building transformations from one problem

to another. To get around this problem, we will give our Turing machines a

write-only output tape, on which the output may be written from left to right.

The space used on the output tape is not considered when calculating space

bounds.

Deﬁnition 13.6.1. A decision problem A is log-space reducible to a decision

problem B, written A ≤

log

B, if there is a function f computable in logarithmic

space that takes instances of A to instances of B in such a way that

∀x: x ∈ A ⇔ f(x) ∈ B.

Just as we have been using the abbreviation polynomially reducible for

polynomial-time reducible, so now we will use the abbreviation logarithmically

reducible for reducible in logarithmic space. This doesn’t lead to confusion

since we can’t do meaningful computation in logarithmic time, and polynomial

space contains all of

PSPACE.

Deﬁnition 13.6.2. Let C be a complexity class. A problem A is C-complete

with respect to logarithmic reductions (log-space complete) if A ∈Cand for

every B ∈C, B ≤

log

Since computations in logarithmic space can be simulated in polynomial

time, A ≤

log

B implies A ≤

Logarithmic reductions have the properties that we expect of them:

•≤

log

is transitive.

• If A ≤

log

B and B ∈ DTAPE(log n), then A ∈ DTAPE(log n).

• If C⊇

DTAPE(log n), L is C-complete with respect to logarithmic reduc-

tions, L ∈

DTAPE(log n), then C = DTAPE(log n).

We omit the proofs of these properties which follow the same scheme that

we know from polynomial reductions. The only exception is that for an input

x and the transformation function f, f (x) cannot be computed and stored. So

whenever the jth bit of f (x) is needed, we compute it in logarithmic space,

forgetting the ﬁrst j − 1 bits. Since f(x) has polynomial length, logarith-

mic space suﬃces to keep a counter that records the number of bits of f (x)

that have already been computed. To give these new notions some life, we

introduce two important problems, one of which is

P-complete and the other

NTAPE(log n)-complete with respect to logarithmic reductions.

First we consider the circuit value problem

CVP. An instance of the circuit

value problem consists of a circuit C over the operators AND, OR, and NOT,

and an input a for C. The circuit C has a designated output gate. We must

compute the value C(a) of this gate of C on input a. The practical signiﬁcance

of this problem is clear.

13.6 Complexity Classes Within P 197

Theorem 13.6.3. CVPis P-complete with respect to logarithmic reductions.

Proof.

CVP ∈ P since we can evaluate the gates of C in topological order.

Now let A ∈

P and let M be a deterministic Turing machine that decides

A in polynomial time p(n). Let x be an instance of length n for which we

must check whether x ∈ A. At this point we will make use of a simple result

that we will prove in Theorem 14.2.1, namely, that from a description of M

we can compute in logarithmic space a circuit C

such that for all inputs of

length n, x ∈ A if and only if C

(x) = 1. So our reduction transforms x into

,x)andx ∈ A if and only if (C

,x) ∈ CVP. 

This result is not surprising. If every circuit can be parallelized, that is, can

be rewritten with small depth, then every polynomial-time solvable problem

can be parallelized well.

One of the ﬁrst algorithms that one learns is depth-ﬁrst search (DFS) on

directed and undirected graphs. Depth-ﬁrst search can be used to solve the

problem of directed s-t-connectivity (

DSTCON) – the problem of determining

whether there is a path from vertex s (source) to vertex t (terminal) in a

directed graph G – in linear time.

Theorem 13.6.4.

DSTCON is NTAPE(log n)-complete with respect to loga-

rithmic reductions.

Proof. First we show that

DSTCON ∈ NTAPE(log n). Starting with z = 1 and

v = s we can store a counter z and a vertex v. These are updated by replacing

v by one of the vertices from its adjacency list and increasing the counter z

by 1. If we ever have v = t, then the input is accepted. If the counter ever

reaches z = n without encountering t, then the input is rejected. Clearly this

algorithm accepts precisely those graphs that have a path from s to t.

Now suppose L ∈

NTAPE(log n)andM is a nondeterministic Turing ma-

chine that decides L in space log n. We can assume that there is only one

accepting conﬁguration K

. For every input x there is a conﬁguration graph

G(x) with a vertex for each conﬁguration of M. The graph has an edge from

K to K



if M on input x can get from K to K



in one step. Our instance

f(x)of

DSTCON will be the graph G(x), the source vertex s corresponding

to the initial conﬁguration on input x and the terminal vertex t = K

.By

construction it is clear that x ∈ L if and only if there is a path form s to t

in G(x). Furthermore, the function f can be generated in logarithmic space.

The conﬁgurations have length O(log n), so they can be stored in logarith-

mic space. For each conﬁguration the machine M induces an adjacency list of

immediate successor conﬁgurations. 

By the Theorem of Immerman and Szelepcs´enyi,

DSTCON is also con-

tained in

co-NTAPE(log n). This is surprising since we have a hard time imag-

ining the nondeterministic algorithm for

DSTCON. Only the proof of the

theorem shows us how to obtain such an algorithm. On the other hand,

it is reasonable to suspect that

DSTCON /∈ DTAPE(log n) since otherwise

DTAPE(log n)=NTAPE(log n).