Kozen D.C. Theory of Computation
Подождите немного. Документ загружается.
Hints for Selected Miscellaneou s Exercises 363
53. (b) Show that if there is a string not accepted, then there is one of the
form xy
ω
for |x| and |y | at most 2
O(n log n)
,wheren is the number
of states.
60. (b) Generate a random n × n matrix A such that for all j there ex-
ists i ≥ j such that A
ij
=0.Thereareexactly
n−1
i=0
(q
n
− q
i
)
such matrices, the same as the number of nonsingular matrices.
Construct a linearly independent sequence of vectors x
1
,... ,x
n
starting with the standard basis (columns of the identity matrix),
using the columns of A as coefficients of linear combinations of
previously generated x
i
and standard basis elements.
66. (iii) Use amplification (Lemma 14.1) and the law of sum (Lecture 13).
(iv) Use amplification (Lemma 14.1).
(v) Use Miscellaneous Exercise 63.
(vi) For BP , use amplification (Lemma 14.1).
68. (a) Use Miscellaneous Exercise 6.
69. (c) Simulate M with another Σ
k
oracle machine N that does not make
the oracle queries when M would, but just records the query strings
and guesses the response of the oracle, then verifies the guesses at
the end of the computation. Use (a) and (b) to show that the
guessing can be done either universally or existentially so as not to
increase the number of alternations along any computation path.
70. Induction on the structure of ϕ. Use the stronger induction hypoth-
esis: for any Boolean formula ϕ(x
1
,... ,x
n
) with Boolean variables
x
1
,... ,x
n
and possibly other variables,
ϕ(excl(z,σ
1
,τ
1
),... ,excl(z,σ
n
,τ
n
))
≡ excl(z,ϕ(σ
1
,... ,σ
n
),ϕ(τ
1
,... ,τ
n
)).
89. Approximate ln(1 − δ) with the first few terms of its Taylor expansion.
Recall that
ln(1 + x)=
∞
n=1
(−1)
n+1
n
x
n
364 Hints for Selected Miscellaneo u s Exercises
for |x| < 1.
93. Use Miscellaneous Exercise 92.
94. Writing A(m, n)asA
m
(n), show that A
m+1
(n)=A
n+1
m
(1), where f
n
denotes the n-fold composition of f with itself:
f
0
(x)
def
= x
f
n+1
(x)
def
= f(f
n
(x)).
Use the second characterization of Miscellaneous Exercise 91.
96. Build an instance of PCP such that any nonnull solution is an accepting
computation history of a given TM M on a given input x.LetΣ=
{0, 1,... ,k − 1} for some k and Γ = {0, 1, #}.Letf(0) = #α
0
#and
g(0) = #, where α
0
is the start configuration of M on x.
98. Use the recursion theorem.
99. Enumerate some subset in increasing order.
100. (b) Let M
σ(i)
be a machine that on input x simulates M
i
on inputs
0, 1,... ,x and accepts iff M
i
halts on all 0, 1,... ,x and accepts x.
107. Show that (R ◦ S)
−1
= S
−1
◦R
−1
and (R
−1
)
−1
= R. Using these facts,
show that R ◦ R
−1
◦ R ⊆ R implies R
−1
◦ R ◦ R
−1
⊆ R
−1
.Nowusea
back-and-forth argument as in Lecture 34 to produce a chain h
0
,h
1
,...
of approximations to h : ω → ω, each with finite domain, maintaining
the invariant that each h
n
is one-to-one on its domain and graph h
n
⊆ R.
108. Use effective padding (Lemma 34.2) to assume without loss of generality
that σ and τ are one-to-one, then apply Miscellaneous Exercise 107.
109. Apply Miscellaneous Exercise 107.
113. Use Miscellaneous Exercise 112.
Hints for Selected Miscellaneou s Exercises 365
114. (b) Consider the sets {x | ϕ
x
(x)iseven} and {x | ϕ
x
(x)isodd}.
115. Use the recursion theorem.
116. Use Homework 12, Exercise 2.
118. (a) Show that there exist arbitrarily complex 0,1-valued functions.
121. This has a two-line proof using the recursion theorem.
124. Diagonalize, then use Miscellaneous Exercise 123(b).
125. (b) Let Φ be arbitrary, and define Ψ
i
def
=Φ
i
+ ϕ
i
+1.
127. (c) An enumeration of the constant functions is given by ϕ
const(k)
, k ≥
0. Let Φ be an arbitrary abstract complexity measure. Define a new
complexity measure Ψ by
Ψ
i
(n)
def
=
0, if ∃ki= const(k)andM
k
(k)↑
n
Φ
i
(n)+1, otherwise.
132. Encode COF. Use the set A from Miscellaneous Exercise 110(b), except
include complements of sets in L before constructing A.LetL(M
σ(i)
)=
{f(x) | x ∈ L(M
i
)}∪A,wheref(x)isthexth element of ∼A.
133. Kill three birds with one stone.
135. Enumerate proofs. Build a total recursive function that grows asymp-
totically faster than any provably total recursive function.
137. Use effective padding.
138. The answers may not be what you think.
366 Hints for Selected Miscellaneo u s Exercises
139. This is quite tricky. Check your solution to make sure the following is
not a counterexample.
s
s
s
s
s
s
s
s
s
s
s
s
@
@R
@
@R
@
@R
@
@R
@
@R
@
@R
q
q
q
q
q
q
·
·
·
Solutions to Selected Miscellaneous Exercises
6. Let A ⊆ DSPACE(G(x)), say by a machine M running in space G(x)
on input x.Let
A
def
= {x#
k
| M halts on input x in space k + |x|}
A
def
= {x#
k
| M halts and accepts x in space k + |x|}.
Then both A
,A
∈ DSPACE(n). By assumption, both A
,A
∈
DTIME(T (n)),saybymachinesM
and M
, respectively, running in
time T (n) on inputs of length n. Now build a machine N that, given x,
runs M
on input x#
i
for i =0, 1, 2,... until it accepts, which it must
by the time i = G(x) −|x| atthelatest.Forthemaximumvalueofi
attained, N runs M
on x#
i
to determine whether x ∈ A, and accepts
or rejects accordingly. Thus L(N)=A.Foreachxa
i
,thesimulation
takes time T (i + |x|), which by monotonicity of T is at most T (G(x)).
Thus the total time is at most (G(x) −|x| +2)T (G(x)).
17. See [63, pp. 377ff.]. Here is a simpler proof using alternating TMs. By the
relationship between deterministic time and alternating space (Corol-
lary 7.5), it suffices to show that nondeterministic and deterministic
S(n)-space-bounded APDAs are equivalent to S(n)-space-bounded al-
ternating TMs.
368 Solutions to Selected Miscellaneo us Exercises
Let M be a nondeterministic S(n)-space-bounded APDA. Assume with-
out loss of generality that M empties its stack before accepting. A con-
figuration consists of worktape contents, state of the finite control, work-
tape head position, and the symbol on the top of the stack or a special
flag indicating that the stack is empty. It does not include the stack con-
tents below the top symbol. Configurations can be represented in S(n)
space.
For configurations α, β and stack σ,writeα → β if there is a computa-
tion starting in configuration α with stack σ and ending in configuration
β with stack σ that does not pop the top element of σ at any time. The
computation may push items on the stack above σ and pop them off
as much as it wants, but it may not touch σ. Note that the question of
whether α → β is independent of σ, because the contents of σ are invis-
ible to the computation except for the top symbol, which is represented
in α and β.
Now we describe a recursive procedure to determine whether α → β.
This can be used to determine whether M accepts x by checking whether
start → accept,wherestart and accept are the start and accept con-
figurations of M , respectively, which we can assume without loss of gen-
erality are unique. The procedure can be implemented on an alternating
TM in S(n) space.
The procedure works as follows. Given α and β, it first checks whether
α = β or whether α derives β in one step without pushing or popping
the stack, and accepts immediately if so. If not, it nondeterministically
guesses whether there exists an intermediate configuration γ such that
α → γ and γ → β. If so, it guesses γ using ∨-branching, then checks in
parallel using ∧-branching that α → γ and γ → β.Otherwise,inorder
for α → β, there must exist α
and β
such that α derives α
in one
step while pushing a symbol on the stack, β
derives β in one step while
popping a symbol off the stack, and α
→ β
by a shorter computation.
The procedure guesses α
and β
, checks that α derives α
in one step
and β
derives β in one step, then calls itself tail recursively to check
whether α
→ β
. There is no need to remember α and β,soatmost
S(n) space is needed.
Conversely, an S(n)-space-bounded alternating TM N can be simulated
by a deterministic S(n)-space-bounded APDA. The APDA simply per-
forms a depth-first search of the computation tree of N, constructing
the tree on the fly and calculating the accept/reject values recursively.
It uses its stack in the depth-first search to remember where it is in the
tree.
Solutions to Selected Miscellaneou s Exercises 369
20. Finitary set operators are chain-continuous: if τ is finitary and C is a
chain,
τ(
C)=
{τ(B) | B ⊆
C,Bfinite}
=
{τ(B) |∃C ∈ C B ⊆ C, B finite}
=
C∈C
{τ(B) | B ⊆ C, B finite}
=
C∈C
{τ(B) | B ⊆ C, B finite}
=
C∈C
τ(C).
That chain-continuous operators are finitary can be shown by transfinite
induction as follows. Recall A ≡ B if there exists f : A
1−1
−→
onto
B.The
cardinality of A is the least ordinal α such that α ≡ A. The cardinality
of A is either finite or a limit ordinal, because α +1≡ α for infinite α
(map β → β for ω ≤ β<α, n → n +1forn<ω,andα → 0).
Now suppose τ is a set operator on X and τ (
C)=
C∈C
τ(C) for any
chain C. For any A ⊆ X,letα be its cardinality and f : α
1−1
−→
onto
A.IfA
is finite, there is nothing to prove. Otherwise, α is a limit ordinal. For
any β<α, define A
β
= {f(γ) | γ<β}. Then the A
β
form a chain and
β<α
A
β
= A. Moreover, all the A
β
are of smaller cardinality because
A
β
≡ β<α, so by the induction hypothesis, τ(A
β
)=
{τ(B) | B ⊆
A
β
,Bfinite}.Then
τ(A)=τ(
β<α
A
β
)
=
β<α
τ(A
β
)bycontinuity
=
β<α
B ⊆ A
β
B finite
τ(B)
=
B ⊆ A
B finite
τ(B).
The last equation follows from the fact that for finite B, B ⊆ A iff
B ⊆ A
β
for some β<α.
370 Solutions to Selected Miscellaneo us Exercises
21. (b) The set operator on subsets of ω given by
A →
A, if A is finite
ω, otherwise
is monotone but not chain-continuous.
23. If τ is chain-continuous, then
τ
ω+1
(∅)=τ(τ
ω
(∅))
= τ(
n<ω
τ
n
(∅))
=
n<ω
τ(τ
n
(∅))
= ∅ ∪
n<ω
τ
n+1
(∅)
=
n<ω
τ
n
(∅)
= τ
ω
(∅).
For an example of a τ whose closure ordinal is ω +1, let X be the set
of nodes of the tree pictured in Lecture 40, p. 264, and let
τ(A)={x | all successors of x are in A}.
Then τ(∅)aretheleaves,τ
2
(∅) are the leaves and the nodes above the
leaves, and so on; τ
ω
(∅) is the set of all nodes except the root; and
τ
ω+1
(∅) is the set of all nodes. This is the least fixpoint.
28. This is a refinement of the proof of Savitch’s theorem given in Lecture 2.
Let M be a nondeterministic TM running in space S(n)andtimeT (n)
on inputs of length n (thus no computation of M on input x uses more
than S(n)spaceorT (n) time). Let start be the start configuration of M
on input x, and assume that M has a unique accept configuration accept
and a unique reject configuration reject (thus no other configuration
halts). Assume also that M erases its worktape and moves all the way
to the left before accepting or rejecting. Let the configurations of M be
encoded as strings over a finite alphabet ∆.
If S(n)andT (n) are constructible in space S(n)logT (n), we can
first compute T (n)andS(n), then call SAV(start, accept,T(n),S(n)),
where SAV(α, β, t, s) is the recursive procedure described in Lecture 2
that attempts to find a computation path from α to β of length at most t
Solutions to Selected Miscellaneou s Exercises 371
through configurations of length at most s. Each recursive instantiation
of SAV requires S(n) space, and the depth of the recursion is log T (n),
giving a space bound of S(n)logT (n).
In case S(n)andT (n) are not constructible, we modify the SAV proce-
dure slightly:
boolean EXACTSAV(α, β, t, s) {
if t =0then return α = β;
if t =1then return α
1
→ β;
for γ ∈ ∆
s
{
if EXACTSAV(α, γ, t/2,s) ∧ EXACTSAV(γ,β,t/2,s)
then return 1;
}
return 0;
}
boolean SAV(α, β, t, s) {
for t
:= 1 to t {
if EXACTSAV(α, β, t
,s) then return 1;
}
return 0;
}
The difference here is that EXACTSAV(α, β, t, s) attempts to find a
computation path of length exactly t from α to β through configurations
of length at most s. Neither SAV nor EXACTSAV uses more than s log t
space.
We first determine S(n)andT (n). We start with S = T =1and
alternately check whether T or S is too small, and if so increment
it by 1 and check again. To check whether T is too small, we call
EXACTSAV(start,α,T,S) for all nonhalting configurations α ∈ ∆
S
in turn. If this procedure ever returns successfully, then T is too small.
To check whether S is too small, we call SAV(start,α,T,S) for all
configurations α ∈ ∆
S
in which the head is scanning the Sth worktape
cell and wants to move its worktape head right, thereby using S +1
space. If this procedure ever returns successfully, then S is too small.
Eventually we find values of S and T just large enough that the en-
tire computation remains within these bounds. At that point we call
SAV(start, accept,T,S).
29. To show that the problem is in PSPACE , we guess a string that is ac-
cepted by all the M
i
and verify that it is accepted. We start with a
372 Solutions to Selected Miscellaneo us Exercises
pebble on the start state of each M
i
, then guess an input string symbol
by symbol, moving pebbles on the states of the M
i
according to their
transition functions. We do not have to remember the guessed string,
just the states that the M
i
are currently in. We accept if we ever get to
a situation in which all pebbles occupy accept states of their respective
automata. Because the pebble configuration can be represented in poly-
nomial space, this is a nondeterministic PSPACE computation. It can
be made deterministic by Savitch’s theorem.
To show that the problem is hard for PSPACE ,letN be an arbitrary
deterministic n
k
-space bounded TM. Assume without loss of generality
that N has a unique accept configuration. Given an input x of length
n, we build a family of n
k
deterministic finite automata M
i
with O(n
k
)
states each whose intersection is the set of accepting computation his-
tories of N on input x.Then
i
L(M
i
)=∅ iff N does not accept x.
Recall that an accepting computation history of N on input x of length
n is a string of the form
#α
0
#α
1
#α
2
# ··· #α
m−1
#α
m
#, (14)
where each α
i
is a string of length n
k
over some finite alphabet ∆ en-
coding a configuration of N on input x, such that
(i) α
0
is the start configuration of N on x,
(ii) α
m
is the accept configuration of N on x,and
(iii) each α
i+1
follows from α
i
according to the transition rules of N.
If a string is an accepting computation history, then it must be of the
correct format (14) and must satisfy (i), (ii), and (iii). Checking that
the input string is of the form (14) requires checking that the input
string is in the regular set (#∆
n
k
)
∗
#, plus some other simple format
checks (exactly one state of N per configuration, each configuration
begins and ends with endmarkers, etc.). This requires an automaton
with O(n
k
) states. Checking (i) or (ii) involves just checking whether
the input begins or ends with a certain fixed string of length n
k
. Again,
each of these conditions can be checked by an automaton with O(n
k
)
states. Finally, to check (iii), recall from the proof of the Cook–Levin
theorem that there is a finite set of local conditions involving the j −1st,
jth, and j + 1st symbols of α
i
and the jth symbol of α
i+1
such that (iii)
holds iff these local conditions are satisfied for all j,1≤ j ≤ n
k
.The
local conditions depend only on the description of N . To check that (iii)
holds, we use n
k
automata with O(n
k
) states. The jth of these automata
scans across and checks for all i that the local condition involving the
j − 1st, jth, and j + 1st symbols of α
i
and the jth symbol of α
i+1
is