Kozen D.C. Theory of Computation

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

332 Hints and Solutions

Homework 5 Solutions

1. Assume that Π

⊆ Σ

. By Theorem 10.2, any set A ∈ Σ

k+1

can be

written

A = {x |∃y |y |≤|x|

∧ R(x, y)}

for some constant c,whereR is a Π

-predicate. By the assumption, R

isalsoaΣ

-predicate, hence so is ∃y |y |≤|x|

∧ R(x, y), and A ∈ Σ

Thus Σ

k+1

⊆ Σ

. The collapse follows by induction on k.

2. (a) We show that under the given assumptions, SAT ∈ P . On input x

of length n, generate the circuit B

and evaluate B

(x). Generating

the circuit can be done in P by the assumption of polynomial-time

uniformity, and evaluation is in P because it is just an instance

of CVP, the circuit value problem, which by Theorem 6.1 is P -

complete.

(b) Using Exercise 1, it suﬃces to show that Π

⊆ Σ

.LetA ∈ Π

and let M be an n

-time bounded Π

oracle machine such that

L(M

SAT

)=A.WeconstructaΣ

machine accepting A as follows.

Let m = n

. On input x of length n, we can construct B

by a

computation: guess the circuit, and then verify that the circuit

is correct by verifying that for all encodings y of Boolean formulas

such that |y | = m,

(y)=1 ⇔ y ∈ SAT. (6)

The circuit is guessed using ∨-branching, then the set of all formu-

las y of length m are generated using ∧-branching, and ﬁnally the

condition (6) can be checked in ∆

(recall ∆

= P

⊆ Σ

∩Π

Thus the whole computation is in Σ

Now to verify x ∈ A in Σ

,weﬁrstguessthecircuitB

(any

correct circuit will do) as described above using ∨-branching, then

check that both

(i) B

is correct, and

(ii) M accepts x,usingB

to answer the oracle queries.

These two facts can be checked simultaneously in Π

3. First we reduce the MAZE problem to the membership problem for

nondeterministic one-counter automata. This shows that the member-

ship problem is hard for NLOGSPACE. Given an instance of the MAZE

Homework 5 Solutions 333

problem consisting of a graph with two distinguished vertices s and t,

transform it into an instance in which the names of the vertices are in-

tegers written in unary notation (that is, n is represented as 0

). This

can be done in logspace. Given such an encoding, a nondeterministic

one-counter automaton can guess a path from s to t,usingitscounter

to hold the name of the vertex it is current visiting.

Now we show that the membership problem is in NLOGSPACE.This

is the harder part of the problem; it is made hard by the fact that the

counter is unbounded. However, we show that if there is an accepting

computation path, then there is one of length at most O(n

), where n

is the size of the input. This will allow us to simulate the one-counter

automaton with a logspace TM, maintaining the counter in binary on

the worktape and counting the number of simulated steps, and halting

if the simulation has not ﬁnished within the allotted time.

Let M be a nondeterministic one-counter automaton. Assume without

loss of generality that if M wants to accept, it empties its counter before

doing so. Let q be the number of states of the ﬁnite control of M.There

are m = q(n+2) possible conﬁgurations of state and input head position

on inputs of length n.

Suppose there is an accepting computation path α of M on input x,

|x| = n.Letc(t) be the value of the counter at time t and let q(t)be

the pair (state, input head position) at time t on α.Amatched interval

is a pair of times (s, t) such that s<t, c(s)=c(t), and c(u) >c(t)

for all u in the range s<u<t.LetN be the maximum value ever

contained in the counter, and let t

be a time such that c(t

)=N.For

1 ≤ i<N,lets

bethelatesttimebeforet

that c(s

)=i, and let t

be the earliest time after t

that c(t

)=i.Then

< ···<s

N−1

< ···<t

and (s

)isamatchedinterval,1≤ i<N.IfN>m

+1, there

must exist 1 ≤ i<j<N such that q(s

)=q(s

)andq(t

)=q(t

Then there is a shorter accepting computation obtained by deleting the

portion of α between s

and s

and between t

and t

We have shown that a minimal accepting computation on x has no

counter value in excess of m

+ 1. There are at most m(m

+ 2) conﬁgu-

rations of state, input head position, and counter value for computations

that do not exceed this bound. If the length of such a computation ex-

ceeds m(m

+ 2), then there must be a repeated conﬁguration, and a

portion of the computation can be deleted to give a shorter accepting

computation. Thus a computation of minimal length is of length at most

m(m

+2)=O(n

334 Hints and Solutions

Homework 6 Solutions

1. (a) If S(n) is space-constructible, there is a machine M that on any

input of length n lays oﬀ exactly S(n) space on its worktape with-

out using more than S(n) space and halts. If M has q states and

d worktape symbols, and if S(n) ≤ o(log n), then the number of

conﬁgurations of state, worktape contents, and worktape head po-

sitionsisatmostqS(n)d

S(n)

, which is less than n/2 for suﬃciently

large n.IfM ever scans all the way to the midpoint of a very

long input string 0

, it must be in a loop by the time it hits the

midpoint. That is, after the last time it sees the left endmarker

and before it gets to the midpoint, it must be in the same conﬁgu-

ration c while scanning two diﬀerent input tape locations i and j,

i<j<n/2, without seeing the left endmarker in between. Because

it sees nothing but 0’s on the input tape after i, it will go through

the same sequence of conﬁgurations starting from j as it did from

i, continuing all the way across until it sees the right endmarker,

which may cause it to change behavior. If we insert a string of 0’s of

length a multiple of p

= j −i ≤ n/2, the machine will not be able

to tell the diﬀerence; it will hit the right endmarker in the same

conﬁguration. The same is true if it scans back again from right

to left; by the time it hits the midpoint, it is in a loop of period

≤ n/2, and so on. We can thus insert a string of 0’s of length

m! for any m ≥ n, which is a multiple of all the possible periods p

of these loops, and the machine will not behave any diﬀerently; in

particular, it will not lay oﬀ any more or less space on its worktape.

This says that S(n + m!) = S(n) for all m ≥ n.

(b) lim inf log log n = ∞.

2. To show that the problem is in PSPACE ,weguessastringthatis

not accepted by M and verify that it is not accepted. We start with a

pebble on the start state of M , then guess an input string symbol by

symbol, moving pebbles on the states of M to mark all states reachable

from the start state under the string guessed so far. We do not have

to remember the guessed string, just the states that M could currently

be in. We accept if we ever get to a situation with no pebble on an

accept state. Because the pebble conﬁguration can be represented in

polynomial space, this is a nondeterministic PSPACE computation. It

can be made deterministic by Savitch’s theorem.

(Note. It is not true that if an NFA accepts all strings of length less than

or equal to the number of states, then it accepts all strings, even over a

single letter alphabet. For example, consider an automaton with a start

Homework 6 Solutions 335

state going to n disjoint loops with pairwise relatively prime lengths

,... ,p

. Make all states accept states except for the one in each

loop farthest from the start state. Then there are 1 + p

+ p

+ ···+ p

states, but the shortest string not accepted is of length p

···p

To show that the problem is hard for PSPACE ,letN be an arbitrary

deterministic n

-space bounded TM. Assume without loss of generality

that N has a unique accept conﬁguration. Given an input x, we build

a nondeterministic ﬁnite automaton M with O(n

) states accepting all

strings that are not accepting computation histories of N on input x.

Then L(F )=Σ

∗

iﬀ N does not accept x. (Thus we are really reducing

L(N)to{M | L(M ) =Σ

∗

}.)

An accepting computation history of N on input x of length n is a string

of the form

#α

# ··· #α

m−1

#α

#, (7)

where each α

is a string of length n

over some ﬁnite alphabet ∆ en-

coding a conﬁguration of N on input x, such that

(i) α

is the start conﬁguration of N on x,

(ii) α

is the accept conﬁguration of N on x,and

(iii) each α

i+1

follows from α

according to the transition rules of N.

If a string is not an accepting computation history, then either it is not of

the form (7), or one of the three conditions (i), (ii), (iii) is violated. The

NFA M guesses nondeterministically which of these to check. Checking

that the input string is not of the form (7) requires checking that the

input string is not in the regular set (#∆

)

∗

#, plus some other simple

format checks (exactly one state of N per conﬁguration, each conﬁgura-

tion begins and ends with endmarkers, etc.). This requires O(n

) states

of M. Checking (i) or (ii) involves just checking whether the input be-

gins or ends with a certain ﬁxed string of length n

. These strings are

encoded in the ﬁnite control of M. Finally, to check (iii), recall from

the proof of the Cook–Levin theorem that there is a ﬁnite set of local

conditions involving the j −1st, jth, and j + 1st symbols α

and the jth

symbol of α

i+1

such that (iii) holds iﬀ these local conditions are satisﬁed

for all j,1≤ j ≤ n

. The local conditions depend only on the descrip-

tion of N. To check that (iii) is violated, M scans across the input, and

at some point guesses nondeterministically where the violation occurs.

It remembers the next three symbols in its ﬁnite control, skips over the

next n

symbols, and accepts if the next symbol is not correct.

336 Hints and Solutions

3. The problem is complete for NLOGSPACE. To show that the problem

is in NLOGSPACE, by exchanging accept and reject states it suﬃces to

ask whether the set accepted is nonempty. This is true iﬀ there exists a

path from the start state to some ﬁnal state. If there are k ﬁnal states,

this is essentially k instances of MAZE.

To show that the problem is hard for NLOGSPACE,wereduceMAZEto

it. Given an instance G =(V, E, s, t) of MAZE, we can assume without

loss of generality that every vertex v has at least one outgoing edge.

Ifnot,addanedgefromv to s; this does not aﬀect the reachability

of t from s.Letm be the maximum outdegree of any vertex and let

Σ={0, 1,... ,m−1}. Build a DFA M with states V , input alphabet Σ,

start state s, unique ﬁnal state t, and transitions obtained by labeling

the edges with elements of Σ in such a way that for each a ∈ Σand

v ∈ V , there is exactly one edge out of v with label a.(Edgesmayhave

more than one label.) Then M is deterministic, and L(M) is nonempty

iﬀ there is a path in G from s to t.

Homework 7 Solutions 337

Homework 7 Solutions

1. The problem is PSPACE-complete. Because every nontrivial ﬁrst-order

theory is PSPACE -hard (Miscellaneous Exercise 49), the interesting

part is showing that it is in PSPACE.

For k-tuples a

,... ,a

and b

,... ,b

of natural numbers, let a

= b

0 and deﬁne

,... ,a

≡

,... ,b

if there is a permutation π : {0, 1,...,k}→{0, 1,... ,k} such that

π(0)

≤ a

π(1)

≤ ··· ≤ a

π(k)

π(0)

≤ b

π(1)

≤ ··· ≤ b

π(k)

(that is, if the a’s and b’s occur in the same order) and for all 0 ≤ i ≤

k −1,

min{2

π(i+1)

− a

π(i)

} =min{2

π(i+1)

− b

π(i)

In other words, for any adjacent pair of a’s and the corresponding ad-

jacent pair of b’s, either their respective distances are less than 2

and

are equal, or both are at least 2

Lemma If

,... ,a

≡

,... ,b

then for all a

k+1

there exists b

k+1

such that

,... ,a

k+1

≡

m−1

k+1

,... ,b

k+1

Proof. Let π be the permutation giving the order of the a’s and the b’s.

Let a

k+1

be arbitrary, and suppose i is the largest number such that

π(i)

≤ a

k+1

.Thuseitheri<kand a

k+1

lies between a

π(i)

and a

π(i+1)

or i = k and a

k+1

is the maximum of a

,... ,a

k+1

. Deﬁne

k+1

⎧

⎨

⎩

π(i+1)

− a

π(i+1)

+ a

k+1

, if i<kand a

k+1

is closer

to a

π(i+1)

than to a

π(i)

+ a

k+1

− a

π(i)

, otherwise.

338 Hints and Solutions

Deﬁne a new permutation ρ : {0, 1,... ,k+1}→{0, 1,... ,k+1} by

ρ(j)=

⎧

⎨

⎩

π(j),j<i,

k +1,j= i,

π(j − 1),j>i.

Then

ρ(0)

≤ a

ρ(1)

≤ ··· ≤ a

ρ(k+1)

ρ(0)

≤ b

ρ(1)

≤ ··· ≤ b

ρ(k+1)

and for all 0 ≤ i ≤ k,

min{2

m−1

ρ(i+1)

− a

ρ(i)

} =min{2

m−1

ρ(i+1)

− b

ρ(i)

therefore

,... ,a

k+1

≡

m−1

k+1

,... ,b

k+1

Now a

,... ,a

≡

,... ,b

implies that a

≤ a

iﬀ b

≤ b

for all 0 ≤

i<j≤ k. This says that a

,... ,a

and b

,... ,b

agree on all atomic

formulas and hence on all quantiﬁer-free formulas. Using this as basis,

an inductive argument using the lemma shows that if a

,... ,a

≡

,... ,b

then

k+1

...Q

k+m

ϕ(a

,... ,a

k+1

,... ,x

k+m

)

iﬀ

k+1

...Q

k+m

ϕ(b

,... ,b

k+1

,... ,x

k+m

This argument is similar to the one given in Lecture 21 for the theory

of dense linear order.

The ≡

-equivalence class of a k-tuple a

,... ,a

can be represented

by a permutation giving the order of the a’s and the distance between

each adjacent pair of a’s up to a maximum of 2

. This information can

be represented in polynomial space. Given such a representation, repre-

sentations of all possible ≡

m−1

k+1

equivalence classes obtained by adding

anewa

k+1

can be generated by a branching computation in polyno-

mial time. This gives rise to an alternating polynomial-time algorithm

to eliminate quantiﬁers similar to the one given in Lecture 21 for the

theory of dense linear order.

Homework 7 Solutions 339

2. These games are examples of so-called Ehrenfeucht–Fraiss´egames.

(a) Round 1: Sonja plays 0 ∈ B; David plays some p ∈ A.

Round 2: Sonja plays 1 ∈ B; David plays some q ∈ A, q>p(if

David plays some q ≤ p, then it is an immediate loss).

Round 3: Sonja plays (p + q)/2 ∈ A. David cannot play between 0

and 1 in B, so Sonja wins.

Note that Sonja wins by taking advantage of the fact that one order

is dense and the other is not.

(b) Both structures are dense linear orders without endpoints, so no

matter where Sonja plays, it is always possible for David to play

on the other structure so as to preserve the order of the pebbles.

to atomic formulas only. Every ﬁrst-order formula can be trans-

formed to an equivalent formula in this form using the following

rules.

¬(ϕ ∨ ψ) ⇒ (¬ϕ) ∧ (¬ψ)

¬(ϕ ∧ ψ) ⇒ (¬ϕ) ∨ (¬ψ)

¬(∃xϕ) ⇒∀x ¬ϕ

¬(∀xϕ) ⇒∃x ¬ϕ

¬¬ϕ ⇒ ϕ.

Let ϕ



be the result of performing this transformation to ¬ϕ.

In one direction, assume that

A |= ϕ and B |= ϕ



where ϕ is a sentence of quantiﬁer depth at most n.Wewanttogive

a winning strategy for Sonja. We show that Sonja can play so as to

maintain the invariant that after k rounds, there is a formula ψ(

of quantiﬁer depth at most n −k and free variables

x = x

,... ,x

such that

A |= ψ(

a)andB |= ψ



(b),

where

a = a

,... ,a

and b = b

,... ,b

are the pebbles played so

far on A and B, respectively. This is true by assumption for k =0.

Nowsupposeitistruefork.

(i) If

ψ(

x)=ψ

(x) ∨ ψ

(x),

then



(x)=ψ



(x) ∧ ψ



(x),

340 Hints and Solutions

hence either

A |= ψ

(a)andB |= ψ



(b)

A |= ψ

(a)andB |= ψ



(b),

say the former without loss of generality. Continue the argu-

ment with the smaller formula ψ

in place of ψ.

(ii) If

ψ(

x)=ψ

(x) ∧ ψ

(x),

the argument is similar to case (i).

(iii) If ψ(

x)isanatomicformulax

≤ x

,then

≤ a

and b

≤ b

which is a win for Sonja.

(iv) If

ψ(

x)=¬ρ(x),

then ρ(

x) is an atomic formula of the form x

≤ x

,thus

≤ a

and b

≤ b

which is again a win for Sonja.

(v) If

ψ(

x)=∃x

k+1

ρ(x, x

k+1

then



(x)=∀x

k+1



(x, x

k+1

)

and

A |= ∃x

k+1

ρ(a, x

k+1

Let Sonja play a pebble on a witness a

k+1

∈ A for the existen-

tial quantiﬁer, so that

A |= ρ(

a, a

k+1

Because

B |= ∀x

k+1



(b, x

k+1

no matter where David plays, we have

B |= ρ



(b, b

k+1

)

and the quantiﬁer depth is one less, so the invariant is main-

tained.

(vi) If

ψ(

x)=∀x

k+1

ρ(x, x

k+1

the argument is similar to (v), except Sonja plays on B instead

of A.

Homework 7 Solutions 341

Conversely, assume that A and B agree on all sentences of quantiﬁer

depth n. Deﬁne

A,a

,... ,a

≡

B,b

,... ,b

if A,a

,... ,a

and B,b

,... ,b

agree on all atomic formulas,

hence on all quantiﬁer-free formulas; that is, for all quantiﬁer-free

formulas ϕ(x

,... ,x

A |= ϕ(a

,... ,a

) ⇔ B |= ϕ(b

,... ,b

For m>0, deﬁne

A,a

,... ,a

≡

B,b

,... ,b

if for all a

k+1

∈ A there exists b

k+1

∈ B such that

A,a

,... ,a

k+1

≡

m−1

k+1

B,b

,... ,b

k+1

and for all b

k+1

∈ B there exists a

k+1

∈ A such that

A,a

,... ,a

k+1

≡

m−1

k+1

B,b

,... ,b

k+1

One can show by an inductive argument that if

A ≡

then David has a winning strategy in the n-pebble game: just place

pebbles so as to maintain the invariant

A,a

,... ,a

≡

n−k

B,b

,... ,b

after k rounds.

We now show that each equivalence class of ≡

is deﬁnable by

aformulawithk free variables and quantiﬁer depth m.Inother

words, for each equivalence class E of ≡

, there is a formula

,... ,x

) with free variables x

,... ,x

and quantiﬁer depth

m such that

A,a

,... ,a

∈ E iﬀ A |= ϕ

,... ,a

Thus if A and B agree on all sentences quantiﬁer depth n,then

they agree on the sentences deﬁning the equivalence classes of ≡

so they must be ≡

-equivalent. Therefore David has a winning

strategy.

The formulas ϕ

are deﬁned inductively. Each equivalence class

of ≡

is deﬁned by a conjunction of atomic formulas or nega-

tions of atomic formulas over the variables x

,... ,x

.Form>0,

the ≡

-equivalence class of A, a,wherea = a

,... ,a

, is deﬁned

as follows. Let E be the set of all ≡

m−1

k+1

-equivalence classes of

a, a

k+1

for all possible choices of a

k+1

∈ A. Although there

may be inﬁnitely many such a

k+1

, there are only ﬁnitely many