Kozen D.C. Theory of Computation

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

342 Hints and Solutions

≡

m−1

k+1

-equivalence classes (this fact follows inductively from this

construction as well). By the induction hypothesis, we have for-

mulas ϕ

(x, x

k+1

) of quantiﬁer depth m − 1 deﬁning E for each

E ∈ E. The formula deﬁning the ≡

-equivalence class of A, a is

then



E∈E

∃x

k+1

(x, x

k+1

) ∧∀x

k+1



E∈E

(x, x

k+1

)

which is of quantiﬁer depth m. This formula describes the set

of possible ≡

m−1

k+1

equivalence classes obtainable by eliminating a

quantiﬁer.

Homework 8 Solutions 343

Homework 8 Solutions

1. The following nondeterministic B¨uchi automaton accepts all and only

(characteristic functions of) ﬁnite subsets of ω. It guesses when it has

seen the last 1 in the input string, and then enters a ﬁnal state, from

which it must see only 0 thereafter; otherwise it goes to a dead state.

There is no deterministic B¨uchi automaton accepting this set. We prove

this by contradiction. Assume that there were such an automaton M

with n states. Consider the action of M on the inﬁnite string (10

n+1

)

When scanning the kth substring of n+1 consecutive 0’s, M must repeat

a state, and one of the states in the loop between the two occurrences

of the repeated state must be an accept state, because M accepts the

string (10

n+1

)

. Therefore M is in some accept state inﬁnitely often

on input (10

n+1

)

, so it erroneously accepts.

2. (a) If addition were deﬁnable in S1S, there would be a nondeterminstic

B¨uchi automaton accepting the set of strings over the alphabet

{0, 1}

representing a, b, c such that a+ b = c. For example, 7 + 4 =

11 would be represented by the string

00000001000000

00001000000000 ··· .

00000000000100

We now use a pumping argument to get a contradiction. Suppose

M has n states. Consider the input string corresponding to the

addition problem (n +1)+(n +1) = 2n +2, which M accepts.

The machine must repeat a state q while scanning the substring

(0, 0, 0)

in the input string between positions n+1 and 2n+2. The

nonnull substring between the two occurrences of q can be deleted

and M erroneously accepts.

(b) We showed in Lecture 25 how to say y ≤ x and A is ﬁnite. To add

the bit vectors represented by A and B, we simulate binary addi-

tion. The low-order bit is leftmost. The carry is given by another

ﬁnite set U. For example,

U = 0000000011101000010100000000000···

A = 0010100111010100101000000000000···

B = 0101000101010001101000000000000···

C = 0111100001101101010100000000000··· .

To assert that U is the carry string, we assert that the low-order

bit of U is 0, and for all i,thei +1stbit of U is 1 if at least two

344 Hints and Solutions

of the ith bits of A, B,andU are 1:

κ(A, B, U)=0∈ U ∧∀x sx ∈ U ↔ ((x ∈ A ∧ x ∈ B) ∨

(x ∈ A ∧ x ∈ U) ∨

(x ∈ B ∧ x ∈ U )).

The sum C is given by the exclusive-or (mod 2 sum) of the bit

strings A, B, and the carry:

ϕ(A, B, C)=∃Uκ(A, B, U) ∧

∀x (x ∈ C ↔ x ∈ A ↔ x ∈ B ↔ x ∈ U).

3. (a) Because B

= 0101010101 ...,wecantake

(x, y)=1

(B)=0∈ B ∧∀xx∈ B ↔ sx ∈ B

(x, y)=∃Bψ

(B) ∧ (x ∈ B ↔ y ∈ B).

Suppose now that we have constructed ϕ

(x, y)andψ

(B). Con-

sider B

as an inﬁnite binary string partitioned into substrings of

n bits as suggested by the deﬁnition in the problem description.

Call these n-bit substrings n-blocks. The position of the ﬁrst bit of

each n-block is a multiple of n. First we construct some auxiliary

formulas.

(x, y)=ϕ

(y, 0) ∧ y ≤ x ∧∀w (ϕ

(w, 0) ∧ w ≤ x)

→ w ≤ y

=“y is the largest multiple of n less than or equal

to x”

(x, y)=ϕ

(x, y) ∧∃zy= sz ∧ ρ

(z,x)

=“x and y are successive multiples of n”

A = {0} = ∀xx∈ A ↔ x =0

A = {n} = ∀xx∈ A ↔ ξ

(0,x)

(A)=∀zz∈ A → ρ

(z,0)

= A ⊆{0, 1,... ,n−1}

Homework 8 Solutions 345

(A, B)=χ

(A) ∧ χ

(B)

∧ (ϕ(A, {0},B) ∨ ϕ(A, {0},B∪{n}))

=“A, B represent binary numbers 0 ≤ n(A),

n(B) ≤ 2

− 1 such that n(B)=n(A)+

1(mod2

)” (here ϕ(A, B, C)isthefor-

mula deﬁned in Exercise 2(b))

(A, z, B, w)=∀x ∀y (ρ(x, z) ∧ ρ(y, w) ∧ ϕ

(x, y))

→ (x ∈ A ↔ y ∈ B)

=“then-blocks of A and B starting at y and

z are the same”

(A, B, y)=σ

(A, 0,B,y) ∧χ

(A)

=“A ⊆{0, 1,... ,n− 1} and the n-blocks of

A starting at 0 and B starting at y are the

same”

(x, y, B)=∀z ∀w (ρ

(x, z) ∧ ρ

(y, w)) → σ

(B,z,B, w)

=“then-blocks containing x and y in B are

the same.”

Note that these formulas depend on ϕ

(B) but not on ψ

(B). We

can now deﬁne

(x, y)=ϕ

(x, y) ∧∃Bψ

(B) ∧ τ

(x, y, B)

=“then-blocks of x and y in B

are the same,

and x and y are in the same position in the

block; that is, x ≡ y (mod n)”

= x ≡ y (mod n2

Once we have ϕ

(x, y), we can construct the auxiliary formulas

(x, y), ξ

(x, y), and so on, as above. Then

(B)=∀y ∀z ∀C ∀D (ξ

(y, z) ∧ υ

(C, B, y)

∧ υ

(D, B, z) → ω

(C, D))

∧∀yρ

(y, 0) → y ∈ B

= “for all pairs of successive multiples of n2

,the

-blocks starting in those two positions repre-

sent numbers in the range {0,... ,2

−1} that

diﬀer by 1 mod 2

, and the ﬁrst block consists

only of 0’s”

= B = B

(b) Using the construction of part (a), one can build formulas of length

n describing strings of length at least 2

. As in the lower bound

proof for the theory of real addition given in Lecture 23, these can

346 Hints and Solutions

be used as “yardsticks” to describe the set of accepting computation

histories of a Turing machine whose running time is 2

Homework 9 Solutions 347

Homework 9 Solutions

1. The problem is PSPACE -complete. Here is an alternating polynomial-

time algorithm. To test Z

|= ∃xϕ(x), we branch existentially, guessing

a ∈ Z

.Eachsucha can be represented by a number {0, 1,... ,n− 1}

in binary, so the depth of the computation tree is linear in the binary

representation of n. Each process at a leaf then tests Z

|= ϕ(a)forits

guessed value of a. To test Z

|= ∀xϕ(x), the procedure is the same,

except universal branching is used. The Boolean connectives ∨ and ∧

can be handled with binary existential branches and binary universal

branches, respectively. We assume negations ¬ have already been pushed

down to the atomic formulas by the De Morgan laws and the rules

¬∃xϕ(x) →∀x ¬ϕ(x)and¬∀xϕ(x) →∃x ¬ϕ(x). We are left with

atomic formulas of the form s = t or s = t,wheres and t are ground

terms over constants in Z

and arithmetic operators · and +. These can

be checked in polynomial time using ordinary arithmetic modulo n.

We show that the problem is hard for PSPACE by a reduction from

QBF.GivenaquantiﬁedBooleanformula

··· Q

B(x

,... ,x

)

of QBF, replace each Boolean variable x

with the atomic formula x

0. This gives a sentence of the language of number theory that is true in

,orinanyZ

for n ≥ 2, iﬀ the original quantiﬁed Boolean formula

was true in the two-element Boolean algebra {0, 1}.

A similar reduction works for all nontrivial ﬁrst-order theories T .All

we need is the existence of a relation R such that T |= ∃

xR(x)and

T |= ∃

x ¬R(x) (this is what is meant by nontrivial). In the application

at hand, we can take R(x)tobex = 0, which is nontrivial provided the

structure has at least two elements.

2. Let

M =(Q, {0, 1},δ,s,F)

be the given Muller automaton. Let Y

be a set variable corresponding

to state q and let X be a set variable corresponding to the input. We

ﬁrst write down an S1S formula run(X,

Y ) describing the runs of M on

input X.ThevariableY

gives the times at which the machine is in

state q.

348 Hints and Solutions

run(X, Y )=0∈ Y

(8)

∧∀n



(n ∈ Y

∧ n ∈ X →



p∈δ(q,0)

s(n) ∈ Y

)(9)

∧∀n



(n ∈ Y

∧ n ∈ X →



p∈δ(q,1)

s(n) ∈ Y

) (10)

∧∀n



p=q

¬(n ∈ Y

∧ n ∈ Y

) (11)

The subformula (8) says that the machine starts at time 0 in its start

state. The subformula (9) says that transitions on input symbol 0 are

correct. Similarly, (10) says that transitions on input symbol 1 are cor-

rect. Finally, the subformula (11) says that the machine is in at most

one state at any time. For any sets A and B

, q ∈ Q,theS1S formula

run(A,

B)istrueiftheB

describe a run of M on input A in the sense

that for all n, n ∈ B

iﬀ the machine is in state q at time n.

We now describe acceptance. Deﬁne

ﬁnite(Y )=∃x ∀yy∈ Y → y ≤ x.

Then ¬ﬁnite(Y

)saysthatM is inﬁnitely often in state q.ForF ⊆ Q,

deﬁne

(Y )=



q∈F

¬ﬁnite(Y

) ∧



q∈F

ﬁnite(Y

This says that F is the IO set of the run described by

Y . Finally, deﬁne

accept(

Y )=



F ∈F

(Y ).

This says that M accepts according to the Muller acceptance condition.

Now take

(X)=∃Y run(X, Y ) ∧ accept(Y ).

3. We ﬁrst show how to simulate polynomial-size circuits B

,... by a

polynomial-time oracle machine M

with a sparse oracle C.Weencode

the circuits B

in the oracle C.

Suppose A ∈{0, 1}

∗

is the set accepted by the circuits. Thus for x ∈

{0, 1}

, x ∈ A iﬀ B

(x) = 1. Because the circuits are of polynomial

Homework 9 Solutions 349

size, there is a constant d and an encoding of circuits B

as strings

∈{0, 1}

such that a Turing machine, given b

and x ∈{0, 1}

,can

compute B

(x) in polynomial time.

Now we save the string b

in the oracle as the characteristic function

of strings of length n.Thatis,forn so large that n

≤ 2

, we put

the ith string of length n in C iﬀ the ith bit of b

is 1. Thus B

can

be determined by querying C on at most n

strings of length n.For

the ﬁnitely many values of n for which n

> 2

, the circuit B

is just

encoded in the ﬁnite control of M.

Because |b

|≤n

, the oracle is sparse. The machine M

on input

x ∈{0, 1}

ﬁrst queries C on the ﬁrst n

strings of length n to determine

, then computes B

(x) and accepts if the value is 1.

For the other direction, suppose we are given a polynomial-time oracle

machine M

with sparse oracle C, |C ∩{0, 1}

|≤n

, accepting a set A.

We wish to construct (nonuniform) polynomial-size circuits B

,...

equivalent to M

. We must somehow encode the oracle information

in the circuits. We do this in two steps. First we show that for each

n there exists a string y

of length polynomial in n encoding all the

oracle information needed by M on inputs of length n. The string y

is essentially a list of all elements in C up to the maximum length that

could be queried by M on inputs of length n. Because these strings are

of polynomial length in n and C is sparse, the string y

is of polynomial

length. More accurately, let n

be the time bound of M . On inputs of

length n, M can only query the oracle on strings of length at most n

because it must write them down. As C is n

-sparse, there are at most

|C ∩{0, 1}

≤n

| =



m=0

|C ∩{0, 1}

|≤



m=0

≤ n

k(d+1)

nonzero elements of C in the range that could possibly be queried by

M on an input of length n, and all of them are of length at most n

so they can be written down end-to-end separated by 2’s in a string

∈{0, 1, 2}

∗

of length at most O(n

k(d+2)

). Now convert the ternary

string z

to binary to get y

.Then

|≤log

3 ·|z

| = O(n

k(d+2)

The binary string y

contains all the oracle information necessary to

process input strings of length n. That is, there is a deterministic

polynomial-time TM N such that for any string x of length n, M

accepts x iﬀ N accepts x#y

.ThemachineN ﬁrst converts y

to z

350 Hints and Solutions

then simulates M on x; whenever M would consult its oracle C, N

searches the list z

Let C

,... be the circuits obtained from Ladner’s construction for

the machine N (Theorem 6.1). Then for any n, C

n+|y

has n + |y

Boolean inputs and is of size polynomial in n+|y

|, which is polynomial

in n,andforanyx of length n, C

n+|y

(x, y

)=1iﬀN accepts x#y

iﬀ M

accepts x. The circuit B

is obtained by specializing the inputs

of C

n+|y

corresponding to y

to the Boolean values in y

Homework 10 Solutions 351

Homework 10 Solutions

1. To construct const,letk be an index for the projection π

and let  be

an index for s

.Then

i = π

(i, x)

= ϕ

(i, x)

= ϕ

(k,i)

(x)

= ϕ



(k,i)

(x)

= ϕ

(,k)

(i)

(x),

so we can take const = ϕ

(,k)

To construct pair,letn be an index for s

and let m be an index for the

partial recursive function

<U ◦ <π

,π

>,U ◦ <π

,π

>>.

Then

<ϕ

,ϕ

>(x)=<ϕ

(x),ϕ

(x)>

= <U(i, x),U(j, x)>

= <U ◦<π

,π

>,U ◦ <π

,π

>>(i, j, x)

= ϕ

(i, j, x)

= ϕ

(m,i,j)

(x)

= ϕ

(m,i,j)

(x)

= ϕ

(n,m)

(i,j)

(x),

so we can take pair = ϕ

(n,m)

2. Let h be a total recursive function that on input <v, j> produces the

index of a function that on input x

(i) computes ϕ

(v, j);

(ii) if ϕ

(v, j)↓, applies ϕ

to ϕ

(v, j); and

(iii) if ϕ

(ϕ

(v, j)) ↓, interprets the result as an index and applies the

function with that index to x.