Kozen D.C. Theory of Computation
Подождите немного. Документ загружается.
Homework 1 275
Homework 1
1. (a) Give a one-tape deterministic O(n log n)-time-bounded Turing ma-
chine accepting a nonregular set.
(b) Show that any set accepted by a one-tape deterministic TM in time
o(n log n) is regular.
2. A k-counter automaton with linearly bounded counters is a one-tape TM
with two-way read-only input head and a fixed finite number of integer
counters that can hold an integer between 0 and n, the length of the
input string. In each step, the machine may test each of its counters for
zero. Based on this information, its current state, and the input symbol
it is currently scanning, it may add one or subtract one from each of the
counters, move its read head left or right, and enter a new state.
(a) Give a formal definition of these machines, including a definition
of acceptance.
(b) Show that a set is in LOGSPACE (NLOGSPACE) iff it is accepted
by a deterministic (nondeterministic) k-counter machine with lin-
early bounded counters for some k.
3. Show that if P = NP then NEXPTIME = EXPTIME .(Hint.Padthe
input with extra #’s).
276 Exercises
Homework 2
1. Show that the reducibility relation ≤
log
m
is transitive: if A ≤
log
m
B and
B ≤
log
m
C,thenA ≤
log
m
C.(Warning. This is nontrivial! You don’t have
enough space to write down an intermediate result in its entirety.)
2. A Boolean formula is in 2-conjunctive normal form (2CNF) if it is a
conjunction of disjuncts of the form ∨
,where and
are literals
(Boolean variables or negations of variables). The problem of deciding
satisfiability of Boolean formulas in 2CNF is denoted 2SAT. Show that
2SAT is complete for co-NLOGSPACE under ≤
log
m
.
3. Show that the value of a given Boolean formula under a given truth
assignment can be computed in deterministic logspace.
4. Consider the nonregular set
B = {$b
k
(0)$b
k
(1)$b
k
(2)$ ···$b
k
(2
k
− 1)$ | k ≥ 0}⊆{0, 1, $}
∗
,
where b
k
(i) denotes the k-bit binary representation of i. Show that
this set is in DSPACE(log log n). Note that it is not enough to give
a deterministic TM for B in which every accepting computation takes
O(log log n) space. According to the official definition, in order to show
that B is in the complexity class DSPACE(log log n), we must give a
deterministic TM for B in which every computation, either accepting,
rejecting, or looping, takes O(log log n) space.
Homework 3 277
Homework 3
1. (a) The set of strings of balanced parentheses is the set generated by
the context-free grammar
S → (S) | SS | ε
Prove that this set is in LOGSPACE.
(b) How about strings of balanced parentheses of two types
S → (S) | [S] | SS | ?
2. Suppose that the game of generalized geography is altered so that ver-
tices can be reused. That is, Players I and II alternate choosing edges
along a directed path (not necessarily simple) starting from a given ver-
tex s and try to force each other into a position from which there is no
next move. What is the complexity of determining whether Player I has
a winning strategy?
3. An alternating finite automaton (AFA) is a 5-tuple
M =(Q, Σ,δ,F,α),
where Q is a finite set of states, Σ is a finite input alphabet, F : Q →
{0, 1} is the characteristic function of a set of final or accept states,that
is,
F (q)=
1, if q is a final state
0, otherwise,
δ is the transition function
δ :(Q × Σ) → ((Q →{0, 1}) →{0, 1}),
and α is the acceptance condition
α :(Q →{0, 1}) →{0, 1}.
Intuitively, F gives a labeling of 0 or 1 at the leaves of the computation
tree, and for all q ∈ Q and a ∈ Σ, the Boolean function
δ(q, a):(Q →{0, 1}) →{0, 1}
278 Exercises
takes a labeling on states and computes a new label for state q;this
is used to pass Boolean labels 0 or 1 back up the computation tree.
Formally, the transition function δ uniquely determines a map
δ :(Q × Σ
∗
) → ((Q →{0, 1}) →{0, 1}),
defined inductively as follows. For q ∈ Q, a ∈ Σ, and x ∈ Σ
∗
,
δ(q, )(u)=u(q)
δ(q, ax)(u)=δ(q, a)(λp.(
δ(p, x)(u))).
The machine is said to accept x ∈ Σ
∗
if
α(λp.(
δ(p, x)(F ))) = 1.
Prove that a set A ⊆ Σ
∗
is accepted by a k-state alternating finite
automaton if and only if its reverse
A
R
= {a
n
···a
1
| a
1
···a
n
∈ A}
is accepted by a 2
k
-state deterministic finite automaton (DFA).
Homework 4 279
Homework 4
1. Prove the following generalization of Savitch’s theorem. For S(n) ≥
log n,
STA(S(n), ∗,A(n)) ⊆ DSPACE(A(n)S(n)+S(n)
2
).
(Hint. Let type : Q →{∧, ∨} be the map in the specification of the
alternating machine telling whether a state in Q is universal or exis-
tential. Extend type to configurations in the obvious way. Consider the
predicate R(α, β, k) = “There is a computation path of length at most
k leading from configuration α to configuration β in which all configura-
tions γ, except possibly β,satisfytype(γ)=type(α).” Use a Savitch-like
argument.)
2. Give a formal definition of a hierarchy over PSPACE with levels
Σ
PSPACE
k
and Π
PSPACE
k
analogous to PH . Show that this hierarchy
collapses to PSPACE .(Hint. Use Exercise 1.)
3. Let H
k
be the complete set for Σ
P
k
defined in Lecture 9:
H
k
= {M$x$
d
| M is a Σ
k
machine accepting x in time
at most d}.
Let #(y) denote the number represented by y in binary. Show that the
set
H
ω
= {y$z | z ∈ H
#(y)
}
is ≤
log
m
-complete for PSPACE .
4. Define a class of sets G
k
similar to H
k
for space instead of time:
G
k
= {M$x$
d
| M is a Σ
k
machine accepting x in space
at most d}.
Show that G
k
is ≤
log
m
-complete for Σ
PSPACE
k
, and that the set
G
ω
= {y$z | z ∈ G
#(y)
}
is complete for exponential time. How do you reconcile this with Exercise
2?
280 Exercises
Homework 5
1. Show that if NP=co-NP,thenPH collapses to NP. More generally,
show that if Σ
p
k
=Π
p
k
then PH collapses to Σ
p
k
.
2. Suppose there exists a sequence of polynomial-size circuits B
0
,B
1
,B
2
,...
for the Boolean satisfiability problem. That is, B
n
has n inputs, one out-
put, and n
O(1)
gates, and given (an encoding over {0, 1}
∗
of) a Boolean
formula x with |x| = n, x is satisfiable iff B
n
(x)=1.
(a) Show that if the sequence B
0
,B
1
,... is polynomial-time uniform
(that is, B
n
can be produced from 0
n
in polynomial time), then
P = NP.
(b) Show that even if the sequence is not polynomial-time uniform,
then PH collapses to Σ
p
3
.
3. In Lecture 5 and Homework 1, Exercise 2, we considered k-counter au-
tomata whose counter values could not exceed n, the length of the in-
put. Without this restriction, it is known that two-counter automata
are as powerful as arbitrary Turing machines (see [61, 76]). Show that
the membership problem for nondeterministic (unbounded) one-counter
automata is complete for NLOGSPACE.(Warning. The difficult part is
to detect looping. Unlike the bounded counter case, there are infinitely
many possible configurations on inputs of length n.)
Homework 6 281
Homework 6
1. In Lecture 3 we showed the existence of an unbounded space-
constructible function S(n) ≤ O(log log n). In this exercise we show
that the function log log n itself is not space constructible.
(a) Prove that for any space-constructible function S(n) ≤ o(log n),
there exists a value k such that S(n)=k for infinitely many n.In
other words,
lim
n≥0
inf
m≥n
S(m) < ∞.
(Hint.IfS(n) is space-constructible, there must be a machine that
on any input of length n lays off exactly S(n) space on its worktape
without using more than S(n) space and halts. Count configura-
tions of state, worktape contents, and worktape head positions (not
read head positions). Consider what happens as the machine scans
across a very long input of the form 0
n
.)
(b) Conclude from (a) that the function log log n is not space-
constructible.
2. Show that the problem of deciding whether L(M )=Σ
∗
for a given non-
deterministic finite automaton (NFA) M is PSPACE -complete. (Hint.
Use computation histories
#α
0
#α
1
# ···#α
N
#,
where each α
i
∈ ∆
∗
is an encoding of a configuration of some TM N
running in PSPACE ,andα
i+1
follows from α
i
in one step according to
the transition rules of N.)
3. What is the complexity of Problem 2 when M is deterministic? Give
proof.
282 Exercises
Homework 7
1. Determine the complexity of the first-order theory of the structure
(ω, ≤), where ω is the set of natural numbers and ≤ is the usual linear
order on ω.
2. Consider the following Ehrenfeucht–Fraiss´e game G
n
between two play-
ers, Sonja (also known in the literature as the Spoiler)andDavid(also
known as the Duplicator). Each player has n pebbles, one of each of n
distinct colors. The players alternate placing the pebbles on elements of
two linear orders A and B. In each round, Sonja plays one of her remain-
ing pebbles on some element of either A or B. David must then play his
pebble of the same color on some element of the other structure. At the
end of n rounds, David is declared the winner if the pebbles occur in the
same order in A as in B (pebble colors are significant when determining
this). Otherwise, Sonja is the winner.
(a) Show that if A is the set of rational numbers and B is the set of
integers, then Sonja has a forced win in G
3
.
(b) Show that if A is the set of rationals and B is the set of reals, then
David has a forced win in G
n
for any n.
(c) Show that David has a forced win in G
n
if and only if A and B agree
on all first-order sentences of quantifier depth n.(Thequantifier
depth of a formula is the maximum number of quantifiers in whose
scope some symbol appears. For example, the formula
∃x ((∀yy≤ x) ∧ (∃zz≤ x))
has quantifier depth two.)
Homework 8 283
Homework 8
1. Show that the set of finite subsets of ω, represented as a set of strings
in {0, 1}
ω
, is accepted by a nondeterministic B¨uchi automaton, but by
no deterministic B¨uchi automaton. (Recall that in B¨uchi acceptance,
F ⊆ Q, and a run σ is accepting if IO(σ) ∩ F = ∅.)
2. (a) Show that integer addition (that is, the predicate “x = y+z”) is not
definable in S1S.(Hint. Use a pumping technique from automata
theory. See [61, Section 4.1] or [76, Lectures 11, 12].)
(b) On the other hand, for a finite set A ⊆ ω, define
n(A)=
x∈A
2
x
.
Let ϕ(A, B, C) be the predicate
“A, B, C are finite sets, and n(A)=n(B)+n(C)”.
Show how to express this in S1S.
3. (a) For n ≥ 1, let B
n
⊆ ω be the set
B
n
= {x | if x = mn + k,0≤ k<n,then
m
2
k
is odd}.
In other words, for any m ≥ 0, the mnth,mn+1st,... ,mn+ n −
1st bits in the {0, 1}
ω
representation of B
n
represent m mod 2
n
in
binary, lowest-order bit first. For example,
B
7
= 0000000
n
1000000
n
0100000
n
1100000
n
0010000
n
... .
Let ϕ
n
(x, y) be the predicate “x ≡ y (mod n)”, and let ψ
n
(B)be
the predicate “B = B
n
”. Construct S1S formulas for ϕ
1
and ψ
1
,
and show inductively how to get short S1S formulas for ϕ
n2
n
and
ψ
n2
n
, given formulas for ϕ
n
and ψ
n
.
(b) Explain informally how you might use (a) to show that S1S is
nonelementary.
284 Exercises
Homework 9
1. Given a sentence ϕ of the first-order language of number theory (addition
and multiplication allowed) and a number n ≥ 2 in binary, what is the
complexity of determining whether ϕ holds in the ring Z
n
of integers
modulo n?Giveproof.
2. Show that for any nondeterministic Muller automaton M with input
alphabet {0, 1}, there is a short formula ϕ
M
(X)ofS1S withonefreeset
variable X such that
L(M)={A ⊆ ω | ϕ
M
(A)}.
(Recall that in Muller acceptance, F ⊆ 2
Q
, and a run σ is accepting if
IO(σ) ∈ F.)
3. Let Σ be a finite alphabet with at least two letters. A set A ⊆ Σ
∗
is
sparse if there is a constant c>0 such that
|A ∩Σ
n
|≤n
c
a.e.
In other words, for all but finitely many n, the number of elements of
A of length n is bounded by a polynomial. Show that P
sparse
,theclass
of sets computable by deterministic polynomial-time oracle machines
with sparse oracles, is exactly the class of sets for which there exist
polynomial-size circuits B
0
,B
1
,..., not necessarily uniform.