Kozen D.C. Theory of Computation

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

316 Miscellaneous Exercises

(b) Prove that the following problem is ≤

-complete for Π

. Given a

recursive binary relation R ⊆ ω

, say by a total Turing machine

accepting the set of pairs in R,isR transitive?

141. Argue that any Π

formula over N can be put into the form (39.1) using

pairing and the skolemization rule

∀x : N ∃f : N → N ϕ(f,x) →∃g : N → (N → N) ∀x : N ϕ(g(x),x).

142. Show that ﬁrst-order number theory is hyperelementary over N but not

elementary (see Lecture 39). Here ﬁrst-order number theory refers to the

set

Th(N)

def

= {ϕ | ϕ is a sentence of the language of ﬁrst-order

number theory and N  ϕ}.

143. Prove Corollary 41.2.

∗∗

144. ([77]) As argued in Lectures 39 and 40, IND programs accept exactly the

sets over N. Show that IND programs with dictionaries accept exactly

the Π

sets over any countable structure. A dictionary is an abstract

data structure that allows data items to be associated with keys and

retrieved by key lookup.

Homework 2 Solutions 323

Homework 2 Solutions

1. If the function f is computable by a logspace transducer, then |f(x)| is

polynomial in |x|, because the transducer can run for at most polyno-

mial time before repeating a conﬁguration. Suppose f and g are com-

putable by logspace transducers M and N, respectively. To compute

g(f(x)), we simulate the computation of N on input f(x). The string

f(x) is not computed in advance, but provided to N symbol by symbol

on a demand basis. Whenever N wishes to read the ith symbol of its

input, the number i is provided to a subroutine that simulates M on

input x from scratch, counting and throwing away all output symbols

until the ith, which it returns to the calling procedure. We need only

enough worktape space to hold the worktapes of M and N and a counter

that can count up to |f (x)|. For more details, see [63, Lemmas 13.1 and

13.2].

2. We ﬁrst show that 2SAT is co-NLOGSPACE-hard by reducing the

MAZE problem, known to be NLOGSPACE-hard, to the complemen-

tary problem, 2CNF unsatisﬁability. Given an instance G =(V, E, s, t)

of MAZE, take V as a set of Boolean variables and consider the 2CNF

formula

= s ∧ (



(u,v)∈E

(u → v)) ∧¬t.

If there is a path from s to t in G, then the clauses in ϕ

corresponding

to the edges in this path imply s → t,thusϕ

implies s ∧ (s → t) ∧¬t,

which is unsatisﬁable. Conversely, if there is no path from s to t, assign

all vertices reachable from s the value 1 and assign all other variables

0. This assignment satisﬁes ϕ

, because s is assigned 1, t is assigned 0,

and there is no clause u → v with u assigned 1 and v assigned 0. Hence

2SAT is hard for co-NLOGSPACE.

We now show that 2SAT is in co-NLOGSPACE, or equivalently, that

2CNF unsatisﬁability is in NLOGSPACE.Givena2CNFformulaB,

the clauses in B contain at most two literals, and we can assume exactly

two without loss of generality by replacing any clause of the form (u)

with (u ∨ u). Now we think of every two-literal clause (u ∨ v)asapair

of implications

(¬u → v)and(¬v → u). (2)

Construct a directed graph G =(V, E) with a vertex for every literal and

directed edges corresponding to the implications (2). It is not diﬃcult to

324 Hints and Solutions

show (see, for example, [75, p. 119]) that B is unsatisﬁable if and only

if there exists a cycle of G containing two complementary literals u, ¬u.

The latter condition can be tested in NLOGSPACE by guessing u,then

guessing and tracing a cycle to verify that it is a cycle and contains u

and ¬u. This requires only logspace to remember u, where we are in the

cycle, and the starting point of the cycle (ﬁnite ﬁngers!).

3. Evaluate the formula recursively as follows. Start at the root. To evaluate

a subformula ϕ ∧ ψ,ﬁrstevaluateϕ; if the value is 1 then the value of

the entire expression is the value of ψ, otherwise it is 0 and ψ need not

be evaluated. Dually, to evaluate ϕ ∨ ψ,ﬁrstevaluateϕ;ifthevalueis

0 then the value of the entire expression is the value of ψ,otherwiseit

is 1 and ψ need not be evaluated. To evaluate ¬ϕ,weevaluateϕ and

then negate the result. We need only ﬁnitely many ﬁngers to walk the

tree, so this can be implemented in logspace.

4. Let

B = {#b

(0)#b

(1)#b

(2)# ···#b

− 1)# | k ≥ 0}

= {#u

# ···#u

−1

# | m ≥ 0,b

(i) ≡ u

(mod 2

0 ≤ i ≤ m2

− 1}

=#0

(#((0 + 1)

− 0

− 1

))

∗

where b

(i) denotes the j-bit binary representation of i mod 2

.Strings

in B

consist of sequences of strings u ∈ (0 + 1)

∗

of length at least j

separated by # such that the low-order j bits of the successive strings

u represent successive integers mod 2

from 0 to m2

− 1forsomem.

Strings in F

consist of successive strings of length k separated by #

such that the ﬁrst string is 0

, the last is 1

, and none of the intermediate

strings are either 0

or 1

Note that

⊇ B

⊇ ··· ⊇ B

B = B

∩ F



j=0

∩ F

To check whether a given string x is in the set B,wecheckthatx is in

, B

, ... , B

, F

in that order. We do it this way so that we do not

use too much space even if the input is not in B.

Homework 2 Solutions 325

The set B

can be recognized in space log j. We just check for successive

substrings u and v whether the low-order j bits represent successive

integers mod 2

by comparing the corresponding low-order j bits of u

and v. We need log j space to count the distance of a bit from the closest

# to its right. We also need to check that the ﬁrst substring u is 0 mod 2

and the last is −1mod2

For j =0, 1, 2,...,welayoﬀlogj tape cells and test membership in

. All strings in B

are of length at least j2

, so if the test succeeds,

then we have used only log j ≤ log log n space. If we ever encounter a

j for which the test fails, we reject immediately; but even in this case,

because x ∈ B

j−1

,wehaveusedonly

log j ≤ 1 + log(j − 1) ≤ 1+loglogn

space. If all tests x ∈ B

aresuccessful,thenwehavelaidoﬀlogk space,

which is suﬃcient to check membership in F

326 Hints and Solutions

Homework 3 Solutions

1. (a) Let #L(x) (respectively, #R(x)) be the number of left (respec-

tively, right) parentheses in the string x. One can show by induction

that a string x is balanced iﬀ

(i) #L(x)=#R(x), and

(ii) for every preﬁx y of x,#L(y) ≥ #R(y),

hence we can just scan left to right, counting #L(y) − #R(y).

(b) A string x of two types of parentheses is balanced iﬀ it satisﬁes the

conditions (i) and (ii) of part (a) irrespective of parenthesis type,

and each matching pair has the same type. One can ﬁnd matching

pairs by counting. In the string x[y] z, the brackets shown match

iﬀ y satisﬁes (i) and (ii) irrespective of parenthesis type.

2. This version of the game is complete for ALOGSPACE = P. Because

vertices can be reused, a board position consists only of the vertex cur-

rently being visited and a bit to tell whose move it is. We do not have to

remember which vertices have already been played as with the previous

version. It requires only logspace to maintain the current board, so an

alternating logspace machine can determine whether the ﬁrst player has

a forced win, thus the problem is in ALOGSPACE = P.

To show that the problem is hard for P, we reduce the circuit value

problem to it. Given an instance of CVP, ﬁrst transform it into an

instance in which there are no negations and the alternation is strict.

To get rid of negations, produce the dual of the circuit:

Original Dual

:= c

∧c



:= c



∨ c



:= c

∨c



:= c



∧ c



:= 0 c



:= 1

:= 1 c



:= 0

:= ¬c



:= ¬c



Then replace all c

:= ¬c

with c

:= c



and c



:= ¬c



with c



:= c

To make the alternation strict, simultaneously replace each statement

:= c

∧c

with the two statements c

:= d ∨d and d := c

∧c

,where

d is a new variable, and each statement c

:= c

∨ c

with the three

statements c

:= d ∨ e, d := c

∧ c

, e := c

∧ c

where d and e are new

variables. This at most triples the number of variables.

Now we make this into a geography game. Note that a player wins by

trapping the opponent in a cul-de-sac (a vertex with outdegree 0). We

Homework 3 Solutions 327

produce a graph with vertices {c

| 0 ≤ i ≤ n}∪{⊥}, directed edges

)and(c

) for each statement c

:= c

∧ c

or c

:= c

∨ c

and edges (c

, ⊥) for each statement c

:= 1. Thus the cul-de-sacs are ⊥

and the c

such that the statement c

:= 0 appears in the circuit. The

starting position is c

, the variable with the highest index. The ﬁrst

player has a forced win iﬀ the value of the circuit is 1.

3. See [63] or [76] for background on ﬁnite automata. In deterministic as

well as alternating ﬁnite automata, it is technically convenient to con-

sider F to be the characteristic function of the set of ﬁnal states rather

than the set of ﬁnal states itself. That is, F : Q →{0, 1} such that

F (q)=



1, if q is a ﬁnal state

0, otherwise.

To construct a DFA from an AFA, let

A =(Q

, Σ,δ

,α

)

be the given AFA, |Q

| = k.LetQ

be the set of all functions Q

→

{0, 1}. Deﬁne the DFA

D =(Q

, Σ,δ

where

(u, a)(q)=δ

(q, a)(u)(3)

= α

(4)

= F

. (5)

To construct an AFA from a DFA, let

D =(Q

, Σ,δ

)

be the given DFA, |Q

| = k.LetQ

be any set of size log k and

identify each element of Q

with a distinct function Q

→{0, 1}. Deﬁne

the AFA

A =(Q

, Σ,δ

,α

where δ

, F

,andα

are deﬁned such that (3)–(5) hold. For u ∈ Q

deﬁne δ

(q, a)(u) arbitrarily.

328 Hints and Solutions

In both reductions, one can show by induction on |x| that for any q ∈

, u ∈ Q

,andx ∈ Σ

∗

(u, x)(q)=

(q, rev x)(u),

where

: Q

× Σ

∗

→ Q

is the multistep version of δ

derived by

induction on the length of the input string:

(u, ε)

def

= u

(u, xa)

def

= δ

(

(u, x),a).

Thus

x ∈ L(D) ⇔ F

(

,x)) = 1

⇔ α

(

,x)) = 1

⇔ α

(λq.(

,x)(q))) = 1

⇔ α

(λq.(

(q, rev x)(F

))) = 1

⇔ rev x ∈ L(A).

Homework 4 Solutions 329

Homework 4 Solutions

1. First assume A(n)andS(n) are space constructible. Let M be an A(n)-

alternation-bounded, S(n)-space-bounded machine. Let C

be the set

of conﬁgurations of M on inputs of length n. There is a ﬁxed constant

c depending only on M such that |C

|≤c

S(n)

Let type : C

→{∧, ∨} tell whether a conﬁguration is universal or

existential. Accept conﬁgurations are universal conﬁgurations without

successors and reject conﬁgurations are existential conﬁgurations with-

out successors. For α, β ∈ C

,write

R(α, β, k)

if there is a computation path from α to β of length at most k such that

all conﬁgurations γ along the path except β satisfy type(γ)=type(α),

and type(β) =type(α). For α, β ∈ C

, the predicate

R(α, β, c

S(n)

)

is decidable in nondeterministic space S(n), therefore it is decidable in

deterministic space S(n)

by Savitch’s theorem.

Then, for input x of length n with initial existential conﬁguration α

M accepts iﬀ

∃α

R(α

,α

S(n)

) ∧

∀α

R(α

,α

S(n)

) →

∃α

R(α

,α

S(n)

) ∧

∀α

R(α

,α

S(n)

) →

...

Qα

A(n)

R(α

A(n)−1

,α

A(n)

S(n)

This can be checked by a Boolean-valued recursive procedure S(α)that

works as follows. If α is existential, it cycles through all β lexicographi-

cally, checking for the existence of a β such that R(α, β, c

S(n)

)andS(β).

It checks the former using the Savitch algorithm, and if that succeeds, it

checks the latter by a recursive call. Similarly, if α is universal, it cycles

through all β, checking that if R(α, β, c

S(n)

)thenS(β).

Each recursive instantiation of the procedure needs S(n)spacetosave

the current conﬁguration α across recursive calls, and the depth of the

recursion is A(n), so A(n)S(n) space is needed in all for this purpose.

In addition, the Savitch procedure to compute R requires S(n)

space,

which can be reused. This gives a total space bound of A(n)S(n)+S(n)

330 Hints and Solutions

When A(n)andS(n) are not space constructible, we try iteratively all

values of A and S such that AS + S

=1, 2,... .

2. Deﬁne a hierarchy over PSPACE by setting

PSPACE

= STA(n

O(1)

, ∗, Σk)

PSPACE

= STA(n

O(1)

, ∗, Πk).

Then by the previous exercise,

PSPACE

= STA(n

O(1)

, ∗, Σk)



c>0

STA(n

, ∗, Σk)

⊆



c>0

DSPACE(kn

+ n

)

⊆ Σ

PSPACE

3. The set H

= {y$z | z ∈ G

#(y)

} is in PSPACE, because a universal

alternating machine on input y$M $x$

can simulate M on x, checking

oﬀ one $ for every step simulated and decrementing the binary number y

for every alternation. Each step of M requires at most polynomial time

in d and the length of M to simulate, and there are at most d steps.

If either the time bound or the bound on the number of alternations is

exceeded, that process of the simulating machine rejects.

To show that H

is hard for PSPACE, it suﬃces to reduce an arbitrary

set in APTIME to H

.LetM be any alternating machine running in

time n

. Then the map

x → y$M$x$

|x |

where #(y)=|x|

, constitutes a ≤

log

reduction from L(M )toH

4. The set

= {M$x$

| M accepts x in at most d space and k

alternations, beginning with ∨}

is in STA(n

, ∗, Σk). On input M$x$

, simulate M on input x. Because

each tape symbol requires at most |M | space to represent on the tape

of the simulating machine (assuming the tape symbols are represented

explicitly in the description of the machine), the simulation requires no

Homework 4 Solutions 331

more than d ·|M | space to represent the tape of M.ThesetG

is also

hard for Σ

PSPACE

:letM be any Σ

machine running in space n

.Then

the map

x → M$x$

|x |

constitutes a ≤

log

reduction from L(M )toG

Now let

= {y$z | z ∈ G

#(y)

}

= {y$M$x$

| M accepts x in at most d space and #(y)

alternations, beginning with ∨}.

The set G

is in APSPACE = EXPTIME via a simulation similar to

the one in the previous problem. To show that it is hard for APSPACE,

let M be an n

space bounded ATM and let e be a constant depending

only on M such that the number of distinct conﬁgurations of M on

inputs of length n is bounded by e

. Then the map

x → y$M$x$

|x |

where #(y)=e

|x |

, constitutes a ≤

log

reduction from L(M)toG