Kozen D.C. Theory of Computation

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

Homework 10 285

Homework 10

1. Using the s

functions and the universal function U, construct total

recursive functions pair and const such that

pair(i,j)

= <ϕ

,ϕ

> ϕ

const(i)

= κ

The construction should be similar to the construction of comp given in

Lecture 33.

2. In the recursion theorem (Theorem 33.1), we proved that for any total

recursive function σ, there exists an index i such that ϕ

σ(i)

= ϕ

. Show

that such an i can be obtained eﬀectively from an index for σ.Thatis,

show that there is a total recursive function ﬁx such that for all j such

that ϕ

is total,

(ﬁx(j))

= ϕ

ﬁx(j)

3. Show that every total recursive function σ has inﬁnitely many ﬁxpoints;

moreover, an inﬁnite list of such ﬁxpoints can be enumerated eﬀectively.

286 Exercises

Homework 11

1. The jump operation (



) is deﬁned as follows:



= K

= {x | ϕ

(x)↓}.

This is the halting problem relativized to A. Deﬁne

(0)

= A

(n+1)

=(A

(n)

)



Show that ∅

(n)

is ≤

-complete for Σ

, n ≥ 1.

2. (a) Show that if A is ≤

-complete for Σ

, n ≥ 1, then A



as deﬁned

in the previous exercise is not in Σ

(b) Conclude from (a) that Σ

and Π

are incomparable with respect

to set inclusion for all n ≥ 1.

3. Consider the following three relativized versions of the recursion theo-

rem.

(a) For any total recursive function σ : ω → ω,thereisann such that

= ϕ

σ(n)

(b) For any total function σ

: ω → ω recursive in A,thereisann

such that ϕ

= ϕ

(n)

: ω → ω recursive in A,thereisann

such that ϕ

= ϕ

(n)

Two are true and one is false. Which is which? Give two proofs and a

counterexample.

4. Recall that a directed graph is strongly connected if for any pair of ver-

tices (u, v) there exists a directed path from u to v. Show that the fol-

lowing problem is ≤

-complete for Π

: given a recursive binary relation

E ⊆ ω

, is the inﬁnite graph (ω,E) strongly connected?

Homework 12 287

Homework 12

1. (a) Show that for every IND program over the natural numbers, there is

an equivalent IND program with simple assignments y := e(

y) but

without existential assignments y := ∃.(Hint. Convert countable

existential branching to ﬁnite existential branching ﬁrst, using the

construct 

∨

; then get rid of ﬁnite existential branching.) Why

can we not eliminate y := ∀ in the same way?

(b) Recall that a binary relation is well-founded if there are no inﬁnite

descending chains. Using (a), show that the following problem is

-complete. Given a recursive binary relation R ⊆ ω

, is it well-

founded?

2. G¨odel deﬁned the µ-recursive functions to be the primitive recursive

functions (see Miscellaneous Exercise 91) with the addition of an extra

programming construct, namely unbounded minimization:iff : ω

→ ω

is a µ-recursive function, then so is

g(x)

def

= µy.(f(x, y)=0),

where the expression on the right-hand side denotes the least y such that

f(x, z)↓ for all z ≤ y and f(x, y)=0,ifsuchay exists, and is undeﬁned

otherwise. Prove axiomatically (that is, using the constructs based on

the s

and universal function properties as described in Lecture 33) that

if f is a partial recursive function, then so is g, and an index for g can

be obtained from an index for f eﬀectively. You may use the conditional

test ϕ

cond(i,j)

of Miscellaneous Exercise 111 without proof.

3. Show that there exists a function T (n) such that DTIME (T (n)) =

DSPACE(T (n)).

Miscellaneous Exercises

The annotation

indicates that there is a hint for this exercise in the Hints

section beginning on p. 361, and

indicates that there is a solution in the

Solutions section beginning on p. 367. The number of stars indicates the

approximate level of diﬃculty.

1. Prove Theorem 3.2.

2. Show that the set {0

| n ≥ 0} requires Ω(log n) space.

3. Prove the following simulation results.

(a) For constants k>1andε>0, any k-tape TM running in time T (n)

can be simulated by a k-tape TM running in time εT (n)+O(n).

(b) For constant ε>0, any 1-tape TM running in time T (n)canbe

simulated by a 1-tape TM running in time εT (n)+O(n

T (n) can be simulated by a 1-tape TM running in time T (n)

∗

(d) For T (n) ≥ n and constant k>1, any k-tape TM running in

time T (n) can be simulated by a 2-tape TM running in time

T (n)logT (n).

290 Miscellaneous Exercises

4. Prove that NSPACE (n

)  NSPACE (n

) for any ﬁxed t>s≥ 1using

the padding technique of Lecture 3.

∗∗

5. Prove the following generalization of Miscellaneous Exercise 4 using the

padding technique of Lecture 3. Let S

: R → R be real-valued func-

tions of a real variable satisfying appropriate constructibility conditions

such that

(a) S

and S

are monotonically increasing;thatis,ifm<n, then

(m) <S

(n)andS

(m) <S

(n); and

(b) there exists ε>0 such that S

(n)

1+ε

≤ O(S

(n)).

Then NSPACE(S

(n))  NSPACE (S

(n)).

6. Sometimes it is useful to reﬁne complexity analysis to distinguish the

time or space usage of a TM on diﬀerent inputs of the same length. For

G :Σ

∗

→ N, deﬁne

DTIME(G(x))

def

= {L(M) | M is a deterministic TM that

takes no more than G(x)steps

on input x}

DSPACE(G(x))

def

= {L(M) | M is a deterministic TM that

uses no more than G(x)work-

tape cells on input x}.

For S : N → N, DTIME(S(n)) and DSPACE(S(n)) are deﬁned as usual

(see Lecture 2). Prove that if T : N → N is monotone and

DSPACE(n) ⊆ DTIME(T (n)),

then for any G :Σ

∗

→ N such that G(x) ≥|x|, constructible or not,

DSPACE(G(x)) ⊆ DTIME(G(x)T (G(x))).

7. Show that any TM that writes at most o(log n) symbols on inputs of

length n accepts a regular set.

8. (a) Show that if M writes no more than t(n) symbols and runs for no

more than T (n) steps, then T (n)isO(t(n)

(b) Show that this bound for T (n)intermsoft(n) is the best possible

for one-tape TMs.

Miscellaneous Exercises 291

9. A k-headed ﬁnite automaton (k-FA) is a one-tape TM with k read-only

input heads that can move left or right but cannot move oﬀ the input

string.

(a) Give a formal deﬁnition of these machines, including a deﬁnition

of acceptance.

(b) Show that a set is in LOGSPACE (NLOGSPACE) iﬀ it is accepted

by a deterministic (nondeterministic) k-FA for some k.

10. A Boolean formula is in 3-conjunctive normal form (3CNF) if it is a

conjunction of clauses of the form 

∨ 

,wherethe

are lit-

erals (Boolean variables or negations of variables). Show that 3CNF-

satisﬁability is NP-complete under ≤

log

11. Give a set that is complete for NSPACE(n) with respect to linear-

time many–one reductions. Conclude that your set is in DSPACE (n)

iﬀ NSPACE(n)=DSPACE(n).

12. Show that if NSPACE (n)=DSPACE(n), then NSPACE(S(n)) =

DSPACE(S(n)) for all S(n) ≥ n.

13. Show that NSPACE(log n) ∩{a}

∗

= DSPACE (log n) ∩{a}

∗

iﬀ

NSPACE(n)=DSPACE (n).

14. Prove that DSPACE(n) = P and DSPACE(n) = NP .

15. Show that the following two problems are ≤

log

-complete for NLOGSPACE.

(a) Given a nondeterministic ﬁnite automaton, does it accept any

string?

(b) Given a nondeterministic ﬁnite automaton, does it accept inﬁnitely

many strings?

16. Let ≤

denote the polynomial-time-bounded Turing reducibility rela-

tion. Show that

(a) ≤

is transitive, and that

(b) ≤

reﬁnes ≤

292 Miscellaneous Exercises

∗∗S

17. An auxiliary pushdown automaton (APDA) is a TM equipped with a

single stack in addition to its worktape. In each step it can check for an

empty stack, and if it is nonempty, read the top element. It also reads the

symbols currently being scanned on its input and worktape. Based on

this information and its current state, it can push or pop a symbol from

a ﬁnite stack alphabet, write a symbol on its worktape, move its input

and worktape heads one cell in either direction, and enter a new state.

It may not read an element of the stack without popping the elements

above it oﬀ. Show that deterministic or nondeterministic APDAs with

S(n) workspace accept exactly the sets in DTIME (2

O(S(n))

18. A map h :Σ

∗

→ Γ

∗

is a homomorphism if h(xy)=h(x)h(y) for all

strings x, y ∈ Σ

∗

. It follows that h(ε)=ε. A homomorphism is non-

erasing if h(a) = ε for any a ∈ Σ. A family of sets C is closed un-

der nonerasing homomorphisms if for any nonerasing homomorphism

h, {h(x) | x ∈ A}∈C whenever A ∈ C.

(a) Show that NP is closed under nonerasing homomorphisms.

(b) Show that P is closed under nonerasing homomorphisms iﬀ P =

NP.

19. Recall from Supplementary Lecture A that a complete partial order is

asetU with a partial order ≤ deﬁned on it such that every subset

A ⊆ U has a supremum (least upper bound) sup A. Show that every

subset A ⊆ U also has a unique inﬁmum (greatest lower bound) inf A

satisfying the following properties.

(a) For all y ∈ A,infA ≤ y (inf A is a lower bound for A).

(b) If for all y ∈ A, x ≤ y,thenx ≤ inf A (inf A is the greatest lower

bound).

∗∗S

20. Prove that a set operator is ﬁnitary iﬀ it is chain-continuous.

21. (a) Prove that every chain-continuous operator on any complete partial

order is monotone.

(b) Give an example of a monotone set operator that is not chain-

continuous.

22. Give an example of a complete partial order U , a monotone operator

τ on U,andasetA ⊆ U of preﬁxpoints such that sup A is not a

preﬁxpoint; thus sup A<inf PF

(sup A).

Miscellaneous Exercises 293

23. Prove that if τ is chain-continuous, then its closure ordinal is at most

ω, but not for monotone operators in general.

24. Induction and well-foundedness go hand in hand. A binary relation < on

asetX is well-founded if there is no inﬁnite descending chain x

,...

in X such that x

i+1

for all i ∈ ω. For example, the natural order

< on ω is well-founded, as is the strict subset order ⊂ on any ﬁnite set.

The strict subset order on 2

is not well-founded, because ω ⊃ ω−{0}⊃

ω −{0, 1}⊃··· .

The induction principle for a binary relation < states that for any set

A ⊆ X,

(∀x ((∀yy<x→ y ∈ A) → x ∈ A)) →∀xx∈ A.

Show that this induction principle is valid iﬀ < is well-founded. Feel free

to use the axiom of choice (see Lecture A).

25. (a) Show that for an alternating machine M running in S(n) space,

the root of the computation tree is labeled 0 or 1 within time c

S(n)

for some c (depending only on M and not on n), or not at all.

(b) Using (a), prove that ASPACE(S(n)) =



DTIME(c

S(n)

26. Show that an alternating Turing machine M without negations accepts

x iﬀ there is a ﬁnite accepting subtree of the computation tree on input

x; that is, a ﬁnite subtree T of the computation tree containing the start

conﬁguration such that every ∨-conﬁguration has at least one successor

in T and every ∧-conﬁguration has all its successors in T .

27. Show that if A is ≤

log

-hard for linear space (DSPACE (n)), then A is

also ≤

log

-hard for PSPACE.

28. Let S(n) ≥ log n and T (n) ≥ n. Show that any set accepted by a non-

deterministic S(n)-space and T (n)-time bounded TM can be accepted

by a deterministic TM in space S(n)logT (n). In other words,

STA(S(n),T(n), Σ1) ⊆ STA(S(n)logT (n), ∗, 0).

Do not forget to worry about constructibility.

294 Miscellaneous Exercises

29. Show that the problem of deciding whether



i=1

L(M

)=∅ for a given

set of deterministic ﬁnite automata M

,1≤ i ≤ n is PSPACE -complete.

30. The security of cryptosystems is based on the existence of one-way

functions. For the purposes of this problem, let us deﬁne a one-

way function to be a deterministic-polynomial-time-computable length-

preserving map f :Σ

∗

→ Σ

∗

that is not invertible in deterministic

polynomial time. Here invertible means: given y, either produce some

x such that f(x)=y,orsaythatnosuchx exists. Show that one-way

functions exist if and only if P = NP.

31. Of the following three problems, one is ≤

log

-complete for co-NLOGSPACE

and the other two are ≤

log

-complete for PSPACE. Which is which? Give

proofs.

(a) Given a regular expression α,isL(α)=∅?

(b) Given a regular expression α,isL(α)=Σ

∗

32.

(a) Prove that a set A is in NP iﬀ there is a deterministic polynomial-

time computable binary predicate R and constant c such that

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

∧ R(x, y)}.

(b) More generally, prove Theorem 10.2: a set A is in Σ

iﬀ there is a

deterministic polynomial-time computable (k + 1)-ary predicate R

and constant c such that

A = {x |∃

|x |

∀

|x |

∃

|x |

···Q

|x |

R(x, y

,... ,y

)}.

The bounded quantiﬁers ∃

and ∀

are deﬁned at the end of Lecture

10.

33. Let S(n) ≥ log n.Provethat



STA(S(n), ∗, Σk) ∪ STA(S(n), ∗, Πk)=NSPACE(S(n)).

34. Deﬁne ∆

k+1

= P

, the family of all sets accepted by deterministic

polynomial-time-bounded oracle machines with an oracle in Σ

Miscellaneous Exercises 295

(a) Show that

∪Π

⊆ ∆

k+1

⊆ Σ

k+1

∩Π

k+1

(b) Show that the set of Boolean formulas with exactly one satisfying

assignment is in ∆

log

-complete problem for ∆

, and prove that it is complete.

35. Prove that PH has a ≤

log

-complete set if and only if it collapses.

36. Prove that the circuit value problem for constant-depth circuits is ≤

log

complete for NLOGSPACE.

37. A Boolean decision diagram (BDD) is a directed acyclic graph with a

single source and two sinks, one labeled 0 and the other labeled 1, such

that all non-sink nodes have exactly two exiting edges, one labeled x

and the other labeled

x for some Boolean variable x.Thevalue of a

BDDonatruthassignmentσ is the label of the sink node of the unique

σ-enabled path from the source to a sink, where an edge with literal 

is σ-enabled if σ() = 1. For BDDs, what is the complexity of

(a) determining the value for a given σ?

(b) satisﬁability?

38. Every decision problem has a family of Boolean circuits of size at most

O(n2

) by writing the nth circuit in disjunctive normal form. Prove that

every decision problem has a family of Boolean circuits of size at most

(a) O(2

∗

(b) O(2

/n).

∗∗

39. ([18]) A rectilinear maze is a connected subset of the inﬁnite checker-

board. That is, it is a connected undirected graph whose vertices

are ordered pairs of integers and whose edges are all of the form

((x, y), (x, y + 1)) or ((x, y), (x +1,y)). Show that the MAZE problem

for rectilinear mazes is solvable in deterministic logspace.

40. Give an NC algorithm for ﬁnding a topological sort in a given directed

acyclic graph (V, E). That is, ﬁnd a total ordering < of V that extends

E in the sense that if uEv,thenu<v.