Kozen D.C. Theory of Computation

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

232 Supplementary Lecture J

The collection Φ is called an abstract complexity measure. Time complexity

of Turing machines certainly satisﬁes these axioms, as does space, provided

we consider the space usage on some input undeﬁned if the machine does

not halt on that input.

The functions Φ

are partial recursive functions; moreover, one can ob-

tain an index for Φ

eﬀectively from i (Miscellaneous Exercise 116).

Given an abstract complexity measure Φ, any total recursive function

f deﬁnes a complexity class

def

= {ϕ

| Φ

(n) ≤ f(n)a.e.}.

Note that this is a class of functions, not of the programs that compute

them; thus ϕ

may be in C

, even though Φ

(n) exceeds f(n) i.o.

The gap and speedup theorems presented in Lecture 32 can be refor-

mulated in this more abstract setting. The proof of the gap theorem in this

more abstract setting is a fairly straightforward generalization of the proof

of Theorem 32.1, and we leave it as an exercise (Miscellaneous Exercise

120), but we redo the proof of the speedup theorem explicitly to illustrate

how the Blum axioms capture the essential properties of complexity mea-

sures.

Theorem J.1 (Gap Theorem [21]) Let Φ be an abstract complexity measure. For any

total recursive function f(x) ≥ x, there exists a total recursive function

t such that C

= C

f◦t

. In other words, for any total recursive f(x) ≥ x,

there is a total recursive t such that if Φ

(x) ≤ f (t(x)) a.e., then there is

an index j such that ϕ

= ϕ

and Φ

(x) ≤ t(x) a.e.

Proof. Miscellaneous Exercise 120. 2

Theorem J.2 (Speedup Theorem [17]) Let Φ be an abstract complexity measure. For

all total recursive f, there exists a total recursive g such that for all indices

i for g, there exists another index j for g with f (n, Φ

(n)) < Φ

(n) a.e.

Proof. The proof mimics the proof of the speedup theorem for time

(Theorem 32.2) to a large extent, except we rely only on the axioms for

abstract complexity measures. It will help to understand that proof thor-

oughly before attempting to read this one.

We ﬁrst diagonalize to get a g

for each ϕ

such that, if ϕ

is total and

i is an index for g

,then

(n) >ϕ

(n − i)a.e.

(J.1)

As in Theorem 32.2, “a.e.” and “i.o.” refer to the variable n. Other variables, such as i in this expression,

are regarded as ﬁxed constants.

Abstract Complexity 233

Stage 0Letg

(0) = 0 and D

= ∅.(HereD corresponds to those ma-

chines that have been deleted from the active list in the proof of Theorem

32.2.)

Stage n ≥ 1 Choose the least i, if it exists, such that

(i) i ≤ n

(ii) i ∈ D

n−1

(iii) Φ

(n) ≤ ϕ

(n − i).

If such an i exists, let g

(n)=ϕ

(n)+1andD

= D

n−1

∪{i}.Ifnosuch

i exists, just let g

(n)=0andD

= D

n−1

Denote by ϕ

h(r,0,0)

the above program for g

.Notethatifϕ

(i) ↓ for

all 0 ≤ i ≤ n,thenϕ

h(r,0,0)

(n)↓.Thusifϕ

is total, then ϕ

h(r,0,0)

is total,

and the function g

computed by ϕ

h(r,0,0)

satisﬁes (J.1).

Next we construct an r.e. set of programs such that if ϕ

is total, then

all programs in the set are total, and g

is represented among them i.o.

For 1 ≤ k ≤ m, deﬁne ϕ

h(r,k,m)

by:

Stages 0,... ,m−1Constructϕ

h(r,k,m)

exactly as ϕ

h(r,0,0)

Stage n ≥ m Choose the least i, if it exists, such that

(i) k ≤ i ≤ n

(ii) i ∈ D

n−1

(iii) Φ

(n) ≤ ϕ

(n − i).

If such an i exists, let ϕ

h(r,k,m)

(n)=ϕ

(n)+1 and D

= D

n−1

∪{i}.If

no such i exists, just let ϕ

h(r,k,m)

(n)=0andD

= D

n−1

Again, note that if ϕ

(i)↓ for 0 ≤ i ≤ n − k,thenϕ

h(r,k,m)

(n)↓.Thus

if ϕ

is total, then ϕ

h(r,k,m)

is total. Moreover, we claim that

∀k

∞

∀mϕ

h(r,k,m)

= g

This is true because during the computation of ϕ

h(r,0,0)

, at some stage m,

all i ≤ k that will ever be in some D

are already in D

. Thereafter, the

same candidates for D

are chosen by ϕ

h(r,k,m)

as by ϕ

h(r,0,0)

,sothesame

function g

is constructed.

Here

∞

∀

means “for all but ﬁnitely many ... ” or “for all suﬃciently large ... ”. There is also

∞

∃

,which

means “there exist inﬁnitely many ... ”.

234 Supplementary Lecture J

Finally, we choose an appropriate ϕ

. Deﬁne the recursive operator σ

σ(r)

(0)

def

σ(r)

(n +1)

def

=1+max

k,m≤n

f(n + k, Φ

h(r,k,m)

(n + k)).

By the recursion theorem, σ has a ﬁxpoint r,sothat

(0)

def

(n +1)

def

=1+max

k,m≤n

f(n + k, Φ

h(r,k,m)

(n + k)).

We can show by induction that ϕ

is total. Certainly ϕ

(0)↓ by deﬁnition,

and as argued above, if ϕ

(i) ↓ for all 0 ≤ i ≤ n,thenϕ

h(r,k,m)

(n + k) ↓,

therefore ϕ

(n +1)↓.Butforallk, m, for suﬃciently large n,

(n +1) >f(n + k, Φ

h(r,k,m)

(n + k)),

thus

f(n, Φ

h(r,k,m)

(n)) <ϕ

(n − k +1)a.e.

In particular, for any i such that ϕ

computes g

,by(J.1)wehave

f(n, Φ

h(r,i+1,m)

(n)) <ϕ

(n − i) < Φ

(n)a.e.

As a ﬁnal example of an interesting general theorem that holds of all

abstract complexity measures, we have the union theorem of McCreight and

Meyer [83]. This theorem states that the union of any eﬀective hierarchy of

complexity classes is itself a complexity class deﬁned by a single function.

For example, one consequence of the union theorem is that there exists

a computable function p such that DTIME(p(n)) = P. Again, however,

the function p is nothing natural like 2

(log n)

or n

log log n

or anything of

the sort. As with t in the gap theorem and g in the speedup theorem, it is

constructed by an intricate diagonalization.

Theorem J.3 (Union Theorem [83]) Let f

,... be an r.e. list of total recursive func-

tions such that for all i and n, f

(n) ≤ f

i+1

(n). Then there exists a total

recursive function f such that



In other words, for any recursive function g, there is an index i for g such

that Φ

(n) ≤ f (n) a.e. iﬀ there is an index j for g andanumberk such

that Φ

(n) ≤ f

(n) a.e.

Abstract Complexity 235

Proof. We build a total recursive function f by diagonalization satisfying

the following two conditions.

(i) For all k, f(n) ≥ f

(n)a.e.

(ii) For all i,ifΦ

(n) >f

(n) i.o. for every k,thenf(n) < Φ

(n) i.o.

These two conditions pull f in opposite directions: condition (i) would like

f to be large, and (ii) would like f to be small. However, because we only

have to satisfy (i) a.e. and (ii) i.o., this gives us some ﬂexibility in the

construction. If we can create f satisfying both conditions, we will have

achieved our goal, because (i) guarantees that C

⊆ C

, and (ii) says that

if Φ

(n) ≤ f(n) a.e., then for some j,Φ

(n) ≤ f

(n)a.e.,thusC

⊆



Now we turn to the construction of f . As in the proof of Theorem J.2, we

construct f by diagonalization. We maintain a queue of pairs (i, k), i ≤ k,

which we can view as the conjecture that Φ

(n) ≤ f

(n) a.e. When a con-

jecture is violated, we take some corrective action in terms of the deﬁnition

of f, retract the conjecture, and replace it with a weaker conjecture.

Stage 0 Deﬁne f (0) := 0 and initialize the queue to contain the single

pair (0, 0).

Stage n ≥ 1 Find the ﬁrst conjecture (i, k) on the queue that is violated

at n; that is, such that Φ

(n) >f

(n). If such an (i, k) exists, deﬁne f(n):=

(n), remove (i, k) from the queue, and append (i, k +1) at the back of the

queue. If no such (i, k) exists, deﬁne f(n)=f

(n). In either case, append

(n, n) at the back of the queue.

For any m, there are only ﬁnitely many conjectures (i, k)withk ≤ m

ever on the queue (

m+2

to be exact). Once a conjecture is deleted from

the queue, it never returns. If a conjecture on the queue is violated inﬁnitely

often, it is eventually chosen for deletion. If it is violated at some stage,

then the only way it would not be chosen for deletion at that stage is if

some conjecture ahead of it on the queue is chosen instead, but this can

happen only ﬁnitely many times. At some stage, all conjectures (i, k)with

k ≤ m that will ever be deleted from the queue have already been deleted,

and thereafter f(n) ≥ f

(n). This establishes (i).

For (ii), if Φ

(n) >f

(n) i.o. for every k, then the conjectures (i, k)for

i ≤ k all go on the queue eventually and are all deleted eventually. When

(i, k) is deleted, f(n) is deﬁned to be f

(n) < Φ

(n), so f (n) < Φ

(n). This

happens inﬁnitely often, therefore f(n) < Φ

(n) i.o. 2

The union theorem does not hold without the monotonicity condition

on the f

(Miscellaneous Exercise 126).

More of the theory of abstract complexity measures is explored in Mis-

cellaneous Exercises 116–127.

Lecture 35

The Arithmetic Hierarchy

Let A, B be sets of strings. We say that A is r.e. in B if A = L(M

)

forsomeoracleTMM with oracle B.WesaythatA is recursive in B if

A = L(M

) for some oracle TM M with oracle B such that M

is total;

that is, if membership in A is decidable relative to an oracle for B.Wewrite

A ≤

B if A is recursive in B.Therelation≤

is called Turing reducibility.

We can deﬁne a hierarchy of classes above the r.e. sets analogous to the

polynomial time hierarchy as follows. Fix the alphabet {0, 1} and identify

strings in {0, 1}

∗

with the natural numbers. Deﬁne

def

= {r.e. sets},

∆

def

= {recursive sets},

n+1

def

= {L(M

) | B ∈ Σ

}

= {A | A is r.e. in some B ∈ Σ

∆

n+1

def

= {L(M

) | B ∈ Σ

total}

= {A | A is recursive in some B ∈ Σ

}

= {A | A ≤

B for some B ∈ Σ

def

= {complements of sets in Σ

Thus Π

is the class of co-r.e. sets. The classes Σ

,Π

,and∆

comprise

what is known as the arithmetic hierarchy.

The Arithmetic Hierarchy 237

Here is perhaps a more revealing characterization of the arithmetic hi-

erarchy in terms of alternation of quantiﬁers. This characterization is anal-

ogous to the characterization of the polynomial time hierarchy given in

Theorem 10.2.

Recall that a set A is r.e. iﬀ there exists a decidable binary predicate

R such that

A = {x |∃yR(x, y)}. (35.1)

For example, the halting and membership problems can be expressed

HP = {M#x |∃tMhalts on x in t steps},

MP = {M#x |∃tMaccepts x in t steps}.

Note that the predicate “M halts on x” is not decidable, but the predicate

“M halts on x in t steps” is, because we can just simulate M on input x

with a universal machine for t steps and see if it halts within that time.

Alternatively,

HP = {M#x |∃vvis a halting computation history of M on x},

MP = {M#x |∃vvis an accepting computation history of M on x}.

The class Σ

is the family of all sets that can be expressed in the form

(35.1).

Similarly, it follows from elementary logic that Π

, the family of co-r.e.

sets, is the class of all sets A for which there exists a decidable binary

predicate R such that

A = {x |∀yR(x, y)}. (35.2)

As is well known, a set is recursive iﬀ it is both r.e. and co-r.e. In terms

of our new notation,

∆

=Σ

∩ Π

These results are special cases of the following theorem, which is anal-

ogous to the characterization of PH given in Miscellaneous Exercise 32.

Theorem 35.1 (i) AsetA is in Σ

iﬀ there exists a decidable (n +1)-ary predicate R

such that

A = {x |∃y

∀y

∃y

··· Qy

R(x, y

,... ,y

)},

where Q = ∃ if n is odd, ∀ if n is even.

(ii) AsetA is in Π

iﬀ there exists a decidable (n +1)-ary predicate R

such that

A = {x |∀y

∃y

∀y

··· Qy

R(x, y

,... ,y

)},

where Q = ∀ if n is odd, ∃ if n is even.

238 Lecture 35

(iii) ∆

=Σ

∩Π

Proof. Miscellaneous Exercise 128. 2

One diﬀerence here from our treatment of PH is that we are lacking a

characterization of the arithmetic hierarchy in terms of something analo-

gous to alternating TMs. This deﬁciency is corrected in Lecture 39.

Example 35.2 The set EMPTY

def

= {M | L(M )=∅} is in Π

, because

EMPTY = {M |∀x ∀tM does not accept x in t steps}.

The two universal quantiﬁers ∀x ∀t can be combined into one using the com-

putable one-to-one pairing function (33.1) described in Lecture 33. Thus

EMPTY = {M |∀zMdoes not accept π

(z)inπ

(z)steps}.

Example 35.3 The set TOTAL

def

= {M | M is total} is in Π

, because

TOTAL = {M |∀x ∃tMhalts on x in t steps}.

Example 35.4 The set FIN

def

= {M | L(M) is ﬁnite} is in Σ

, because

FIN = {M |∃n ∀x if |x| >nthen x ∈ L(M)}

= {M |∃n ∀x ∀t |x|≤n or M does not accept x in t steps}.

Again, the two universal quantiﬁers ∀x ∀t can be combined into one using

the pairing function (33.1). 2

Example 35.5 Asetiscoﬁnite if its complement is ﬁnite. The set

COF

def

= {M | L(M) is coﬁnite}

is in Σ

, because

COF = {M |∃n ∀x if |x| >nthen x ∈ L(M)}

= {M |∃n ∀x ∃t |x|≤n or M accepts x in t steps}.

Figure 35.1 depicts the inclusions among the lowest few levels of the

hierarchy. Each level of the hierarchy is strictly contained in the next; that

is, Σ

∪ Π

⊆ ∆

n+1

, but Σ

∪ Π

=∆

n+1

. We know that there exist r.e.

sets that are not co-r.e. (HP, for example) and co-r.e. sets that are not r.e.

(∼HP, for example). Thus Σ

and Π

are incomparable with respect to set

inclusion. One can show in the same way that Σ

and Π

are incomparable

with respect to set inclusion for any n (Homework 11, Exercise 2).

The Arithmetic Hierarchy 239

Reducibility and Completeness

For A ⊆ Σ

∗

and B ⊆ Γ

∗

, deﬁne A ≤

B if there exists a total recursive

function σ :Σ

∗

→ Γ

∗

such that for all x ∈ Σ

∗

x ∈ A ⇔ σ(x) ∈ B.

The relation ≤

is called many–one reducibility and is analogous to the

reducibility relations ≤

log

or ≤

we have studied, except without the re-

source bounds.

The membership problem MP

def

= {M#x | M accepts x} is not only

undecidable but is in a sense a “hardest” r.e. set, because every other r.e.

set ≤

-reduces to it: for any Turing machine M,themapx → M#x is a

trivially computable map reducing L(M)toMP.

We say that a set is r.e.-hard if every r.e. set ≤

-reduces to it. In other

words, the set B is r.e.-hard if for all r.e. sets A, A ≤

B. As just observed,

the membership problem MP is r.e.-hard. So is any other problem to which

the membership problem ≤

-reduces (for example, the halting problem

HP), because the relation ≤

is transitive.

AsetB is said to be r.e.-complete if it is both an r.e. set and r.e.-hard.

For example, both MP and HP are r.e.-complete.

More generally, if C is a class of sets, we say that a set B is ≤

-hard for

C (or just C-hard) if A ≤

B for all A ∈ C.WesaythatB is ≤

-complete

for C (or just C-complete) if B is ≤

-hard for C and B ∈ C.

One can prove a theorem corresponding to Lemma 5.3 that says that

if A ≤

B and B ∈ Σ

,thenA ∈ Σ

,andifA ≤

B and B ∈ ∆

,then

A ∈ ∆

. Because we know that the arithmetic hierarchy is strict (each

level is properly contained in the next), if B is ≤

-complete for Σ

,then

B ∈ Π

(or ∆

or Σ

n−1

It turns out that each of the problems mentioned above is ≤

-complete

for the level of the hierarchy in which it naturally falls:

(i) HP is ≤

-complete for Σ

(ii) MP is ≤

-complete for Σ

(iii) EMPTY is ≤

-complete for Π

(iv) TOTAL is ≤

-complete for Π

(v) FIN is ≤

-complete for Σ

,and

(vi) COF is ≤

-complete for Σ

Because the hierarchy is strict, none of these problems is contained in any

class lower in the hierarchy or reduces to any problem complete for any

class lower in the hierarchy. If it did, then the hierarchy would collapse at

240 Lecture 35

that level. For example, EMPTY does not reduce to HP and COF does not

reduce to FIN.

We have shown (ii) above. We prove (v) here and (vi) in Lecture 36;

the others we leave as exercises (Miscellaneous Exercise 130).

We have already argued that FIN ∈ Σ

, because ﬁniteness can be ex-

pressedwithan∃∀ predicate. To show that FIN is ≤

-hard for Σ

,we

need to show that any set in Σ

reduces to it. We use the characterization

of Theorem 35.1. Let

A = {x ∈ Γ

∗

|∃y ∀zR(x, y, z)}

be an arbitrary set in Σ

,whereR(x, y, z) is a decidable ternary predicate.

Let M be a total machine that decides R. We need to construct a machine

N eﬀectively from a given x such that N ∈ FIN iﬀ x ∈ A.ThuswewantN

to accept a ﬁnite set iﬀ ∃y ∀zR(x, y, z); equivalently, we want N to accept

an inﬁnite set iﬀ ∀y ∃z ¬R(x, y, z). Let N on input w

(i) write down all strings y of length at most |w |;then

(ii) for each such y, try to ﬁnd a z such that ¬R(x, y, z) (that is, such

that M rejects x#y#z), and accept if all these trials are successful.

The machine N has x and a description of M hard-wired in its ﬁnite

control.

In step (ii), for each y of length at most |w |, N just enumerates strings z

in some order and runs M on x#y#z until some z is found causing M to

reject. Because M is total, N need not worry about timesharing; it can just

process the z’s in order. If no such z is ever found, N just goes on forever.

Surely such an N can be built eﬀectively from M and x.

Now if x ∈ A, then there exists y such that for all z, R(x, y, z) (that

is, for all z, M accepts x#y#z); thus step (ii) fails whenever |w |≥|y |.In

this case N accepts a ﬁnite set. On the other hand, if x ∈ A, then for all y

there exists a z such that ¬R(x, y, z), and these are all found in step (ii).

In this case, N accepts Γ

∗

We have argued that L(N)isaﬁnitesetifx ∈ A and Γ

∗

if x ∈ A,

therefore the map x → N constitutes a ≤

-reduction from A to FIN.

Because A was an arbitrary element of Σ

,FINis≤

-hard for Σ

Note that the same reduction shows that TOTAL is ≤

-hard for Π

This is because in the construction above, N is total iﬀ x ∈∼A,and

∼A ∈ Π

because A ∈ Σ

The Arithmetic Hierarchy 241



recursive sets

r.e. sets co-r.e. sets

∆

EMPTY

TOTAL

FIN

COF

Figure 35.1: The arithmetic hierarchy.