Kozen D.C. Theory of Computation

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

212 Supplementary Lecture I

Consider Poisson trials X

,1≤ i ≤ n,withsumX =



and

Pr(X

=1)=p

. An exact expression for the upper tail is

Pr (X ≥ k)=



A ⊆{1,... ,n}

|A |≥k



i∈A



i∈A

(1 − p

In the special case of Bernoulli trials with success probability p,thissim-

pliﬁes to the binomial distribution

Pr (X ≥ k)=



i≥k





(1 − p)

n−i

However, these expressions are algebraically unwieldy. A more convenient

formula is provided by the Chernoﬀ bound.

The Chernoﬀ bound comes in several forms. One form states that for

Poisson trials X

with sum X =



and µ = EX, for any δ>0,

Pr (X ≥ (1 + δ)µ) <



(1 + δ)

1+δ



. (I.3)

Equivalently,

Pr (X ≥ (1 + δ)µ) <



1 −

1+δ



(1+δ)/δ

δµ

. (I.4)

In (I.4), the subexpression



1 −

1+δ



(1+δ)/δ

(I.5)

is a special case of the function (1−1/x)

, which arises frequently in asymp-

totic analysis. It is worth remembering that this function is bounded above

by e

−1

for all positive x and tends to that value in the limit as x approaches

inﬁnity. Similarly, the function (1 + 1/x)

is bounded above by e for all

positive x and tends to that limit as x approaches inﬁnity (Miscellaneous

Exercise 57(a)).

A third form equivalent to (I.3) and (I.4) is: for all k>µ,

Pr (X ≥ k) <e

k−µ

(µ/k)

. (I.6)

One can see clearly from (I.4) and (I.6) that the convergence is exponential

with distance from the mean.

These formulas bound the upper tail of the distribution. There are also

symmetric versions for the lower tail: for any δ such that 0 ≤ δ<1andk

Tail Bounds 213

such that 0 <k≤ µ,

Pr (X ≤ (1 − δ)µ) <



−δ

(1 − δ)

1−δ



(I.7)

−1



1 − δ



(1−δ)/δ

δµ

(I.8)

Pr (X ≤ k) <e

k−µ

(µ/k)

. (I.9)

In the case of the lower tail, we also have a fourth version given by

Pr (X ≤ (1 − δ)µ) <e

−δ

µ/2

. (I.10)

This bound is slightly weaker than (I.7)–(I.9), but is nevertheless very useful

because of its simple form.

Proof of the Chernoﬀ Bound

We now prove the Chernoﬀ bound (I.3) for Poisson trials X

.Itiseasyto

show that the other forms (I.4) and (I.6) are equivalent, and these are left

as exercises (Miscellaneous Exercise 87). The proofs of the corresponding

bounds (I.7)–(I.9) for the lower tail are similar and are also left as exercises

(Miscellaneous Exercise 88). The weaker bound (I.10) requires a separate

argument involving the Taylor expansion of ln(1 − δ), but is not diﬃcult

(Miscellaneous Exercise 89).

Although the success probabilities of the X

may diﬀer, it is important

that the trials be independent. At a crucial step of the proof, we use the

fact that the expected value of the product of independent trials is the

product of their expectations (Miscellaneous Exercise 82).

Let X

be Poisson trials with success probabilities p

,sumX =



and mean µ = EX =



.Fixa>0. By the monotonicity of the expo-

nential function and the Markov bound (I.1), we have

Pr (X ≥ (1 + δ)µ)=Pr(e

≥ e

a(1+δ)µ

)

≤ E(e

) · e

−a(1+δ)µ

. (I.11)

Because the expected value of the product of independent trials is the

product of their expectations (Miscellaneous Exercise 82), and because the

are independent if the X

are, we can write

E(e

)=E(e

)=E(



E(e

)



+(1− p

)) =



(1 + p

− 1)). (I.12)

214 Supplementary Lecture I

It follows from (1 + 1/x)

<ethat 1 + y<e

for all positive y. Applying

this with y = p

− 1), we have 1 + p

− 1) <e

−1)

, thus (I.12) is

strictly bounded by



−1)

= e

−1)

= e

−1)µ

Combining this with the expression e

−a(1+δ)µ

gives a strict bound

−1)µ

· e

−a(1+δ)µ

= e

−1−a−aδ)µ

(I.13)

on (I.11). Now we wish to choose a minimizing e

−1−a−aδ. The derivative

vanishes at a =ln(1+δ), and substituting this value for a in (I.13) and

simplifying yields (I.3).

Lecture 32

The Gap Theorem and Other Pathology

One might get the impression from the structure of the complexity hierar-

chies we have studied that all problems have a natural inherent complexity,

and that allowing slightly more time or space always allows more to be com-

puted. Both these statements seem to be true for most natural problems

and complexity bounds, but neither is true in general. One can construct

pathological examples for which they provably fail.

For example, one can exhibit a computable function f with no asymp-

totically best algorithm, in the sense that for any algorithm for f running

in time T (n), there is another algorithm for f running in time log T (n).

Thus f can be endlessly sped up. Also, there is nothing special about the

log function—the result holds for any total recursive function.

For another example, one can show that there is a space bound S(n)

such that any function computable in space S(n) is also computable in

space log S(n). At ﬁrst this might seem to contradict Theorem 3.1, but

that theorem has a constructibility condition that is not satisﬁed by S(n).

Again, this holds for any recursive improvement, not just log.

Most of the examples of this lecture are constructed by intricate diago-

nalizations. They do not correspond to anything natural and would never

arise in real applications. Nevertheless, they are worth studying as a way

to better understand the power and limitations of complexity theory. We

prove these results in terms of Turing machine time and space in this lec-

216 Lecture 32

ture; however, most of them are independent of the particular measure. A

more abstract treatment is given in Supplementary Lecture J.

The ﬁrst example we look at is the gap theorem, which states that there

are arbitrarily large recursive gaps in the complexity hierarchy. This result

is due independently to Borodin [21] and Trakhtenbrot [122].

Theorem 32.1 (Gap Theorem [21, 122]) For any total recursive function f : ω →

ω such that f (x) ≥ x, there exists a time bound T (n) such that

DTIME(f(T (n))) = DTIME(T (n)); in other words, there is no set ac-

cepted by a deterministic TM in time f (T (n)) that is not accepted by a

deterministic TM in time T (n).

Proof. Let T

(x) denote the running time of TM M

on input x.Foreach

n, deﬁne T (n)tobetheleastm such that for all i ≤ n,ifT

(n) ≤ f(m),

then T

(n) ≤ m. To compute T (n), start by setting m := 0. As long as

there exists an i ≤ n such that m<T

(n) ≤ f(m), set m := T

(n). This

process must terminate, because there are only ﬁnitely many i ≤ n.The

value of T (n) is the ﬁnal value of m.

Now we claim that T (n) satisﬁes the requirements of the theorem. Sup-

pose M

runs in time f(T (n)). Thus T

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

By construction

of T , for suﬃciently large n ≥ i, T

(n) ≤ T (n). 2

What we have actually proved is stronger than the statement of the

theorem. The theorem states that for any deterministic TM M

running

in time f(T (n)), there is an equivalent deterministic TM M

running in

time T (n). But what we have actually shown is that any deterministic TM

running in time f (T (n)) also runs in time T (n).

Of course, all these bounds hold a.e., but we can make them hold ev-

erywhere by encoding the values on small inputs in the ﬁnite control and

computing them by table lookup.

The next example gives a set for which any algorithm can be sped up

arbitrarily many times by an arbitrary preselected recursive amount. This

result is due to Blum [17].

Theorem 32.2 (Speedup Theorem [17]) Let T

(x) denote the running time of TM M

on input x.Letf : ω → ω be any monotone total recursive function such

that f(n) ≥ n

. There exists a recursive set A such that for any TM M

accepting A, there is another TM M

accepting A with f(T

(x)) <T

(x)

a.e.

“a.e.” means “almost everywhere” or “for all but ﬁnitely many n”. Also, “i.o.” means, “inﬁnitely often” =

“for inﬁnitely many n”.

The Gap Theorem and Other Pathology 217

Proof. Let f

denote the n-fold composition of f with itself:

def

= f ◦ f ◦···◦f



 

Thus f

is the identity function, f

= f ,andf

m+n

= f

◦f

. For example,

if f(m)=m

,thenf

(m)=m

,andiff(m)=2

,thenf

(m)isan

iterated exponential involving a stack of 2’s of height n.

We construct by diagonalization a set A ⊆ 0

∗

such that

(i) for any machine M

accepting A, T

) >f

n−i

(2) a.e.,

and

(ii) for all k, there exists a machine M

accepting A such that T

) ≤

n−k

(2) a.e.

This achieves our goal, because for any machine M

accepting A, (ii) guar-

antees the existence of a machine M

accepting A such that T

) ≤

n−i−1

(2) a.e.; but then

f(T

)) ≤ f (f

n−i−1

(2)) a.e. by monotonicity of f

= f

n−i

(2)

) a.e. by (i).

Now we turn to the construction of the set A.LetM

,... be a

list of all one-tape Turing machines with input alphabet {0}.LetN be an

enumeration machine that carries out the following simulation. It maintains

a ﬁnite active list of descriptions of machines currently being simulated. We

assume that a description of M

suitable for universal simulation is easily

obtained from the index i.

The computation of N proceeds in stages. Initially, the active list is

empty. At stage n, N puts the next machine M

at the end of the active

list. It then simulates the machines on the active list in order, smallest

index ﬁrst. For each such M

,itsimulatesM

on input 0

for f

n−i

(2)

steps. It picks the ﬁrst one that halts within its allotted time and does the

opposite: if M

rejects 0

, N declares 0

∈ A,andifM

accepts 0

, N

declares 0

∈ A. This ensures that L(M

) = A. It then deletes M

from the

active list. If no machine on the active list halts within its allotted time,

then N just declares 0

∈ A.

This construction ensures that any machine M

that runs in time

n−i

(2) i.o. does not accept A.ThemachineM

is put on the active list

at stage i. Thereafter, if M

halts within time f

n−i

(2) on 0

but is not

We are regarding f

n−i

(2) as a function of n with i a ﬁxed constant. Thus “i.o.” and “a.e.” in this context

are meant to be interpreted as “for inﬁnitely many n” and “for all but ﬁnitely many n”, respectively.

218 Lecture 32

chosen for deletion, then some higher priority machine on the active list

must have been chosen; but this can happen only ﬁnitely many times. So

if M

halts within time f

n−i

(2) on 0

i.o., then eventually M

will be the

highest priority machine on the list and will be chosen for deletion, say

at stage n.Atthatpoint,0

will be put into A iﬀ 0

∈ L(M

), ensuring

L(M

) = A. This establishes condition (i) above.

For condition (ii), we need to show that for all k, A is accepted by a

one-tape TM N

running in time f

n−k

(2) a.e. The key idea is to hard-code

the ﬁrst m stages of the computation of N in the ﬁnite control of N

for

some suﬃciently large m. Note that for each M

, either

(A) T

) ≤ f

n−i

(2) i.o., in which case there is a stage m(i)atwhichN

deletes M

from the active list; or

(B) T

) >f

n−i

(2) a.e., in which case there is a stage m(i)afterwhich

always exceeds its allotted time.

Let m =max

i≤k

m(i). We cannot determine the m(i)orm eﬀectively

(Miscellaneous Exercise 105), but we do know that they exist. The machine

has a list of elements 0

∈ A for n ≤ m hard-coded in its ﬁnite control.

On such inputs, it simply does a table lookup to determine whether 0

∈ A

and accepts or rejects accordingly. On inputs 0

for n>m,itsimulatesthe

action of N on stages m +1,m+2,... ,nstarting with a certain active list,

which it also has hard-coded in its ﬁnite control. The active list it starts

with is N’s active list at stage m with all machines M

for i ≤ k deleted.

This does not change the status of 0

∈ A:foreachM

with i ≤ k,in

case A it has already been deleted from the active list by stage m,andin

case B it will always exceed its allotted time after stage m, so it will never

be a candidate for deletion. The simulation will therefore behave exactly

as N would at stage m and beyond. The machine N

can thus determine

whether 0

∈ A and accept or reject accordingly.

It remains to estimate the running time of N

on input 0

.Ifn ≤ m, N

takes linear time, enough time to read the input and do the table lookup. If

n>m, N

must simulate at most n−k machines on the active list on n−m

inputs, each for at most f

n−k−1

(2) steps. Under mild assumptions on the

encoding scheme, interpreting the binary representation of the index i as a

description of M

, M

has at most log i states, at most log i tape symbols,

and at most log i transitions in its ﬁnite control, and one step of M

can

be simulated in roughly c(log i)

steps of N

. Thus the total time needed

for all the simulations is at most cn

(log n)

n−k−1

(2). But

(log n)

≤ 2

n−k−1

a.e.

≤ f

n−k−1

(2) because f(m) ≥ m

The Gap Theorem and Other Pathology 219

therefore

(log n)

n−k−1

(2) ≤ (f

n−k−1

(2))

a.e.

≤ f(f

n−k−1

(2))

= f

n−k

(2).

There are a few interesting observations we can make about the proof

of Theorem 32.2.

First, the “mild assumptions” on the encoding scheme are inconsequen-

tial. If they are not satisﬁed, the condition f(m) ≥ m

can be strengthened

accordingly. We only need to know that the overhead for universal simula-

tion of Turing machines is bounded by a total recursive function.

The value m =max

i≤k

m(i) in the proof of Theorem 32.2 cannot be

obtained eﬀectively. We know that for each M

there exists such an m, but

it is undecidable whether M

falls in case A or case B, so we do not know

whether to delete M

from the active list. Indeed, it is impossible to obtain

a machine for A running in time f

n−k

(2) eﬀectively from k (Miscellaneous

Exercise 105).

Lecture 33

Partial Recursive Functions and

G¨odel Numberings

Partial and Total Recursive Functions

The next few lectures are an introduction to classical recursive function

theory. For a more comprehensive treatment of this subject, see [104, 114].

A partial recursive function is a computable partial function f : ω → ω.

Partial means that it need not be deﬁned on all inputs. Computable can

be deﬁned in several equivalent ways: by Turing machines, by G¨odel’s µ-

recursive functions, by the λ-calculus, or by C programs, to name a few. A

partial recursive function is total if it is everywhere deﬁned.

For example, we can deﬁne the partial recursive function computed by

a deterministic Turing machine M to be the partial function f such that

• if M does not halt on input x,thenf(x) is undeﬁned, and

• if M halts on input x,thenf(x) is the value written on M’s tape

when it enters its halt state.

Partial Recursive Functions and G¨odel Numberings 221

Pairing

We consider only unary functions ω → ω. Functions of higher arity can be

encoded using the one-to-one pairing function <>: ω

→ ω:

<i, j>

def



i + j +1



+ i. (33.1)

012345

0 01361015

2 4 7 11 16

5 8 12 17

91318

14 19

The corresponding projections are denoted π

and π

(<x, y>)

def

= xπ

(<x, y>)

def

= y.

For n>2, we take

,... ,x

def

= <x

, <x

,... ,<x

n−1

>>>,

and for m ≤ n,

def

n−1

m−1

◦ π

To save notation, we write f(x, y) instead of f(<x, y>)andf(x

,... ,x

)

instead of f(<x

,... ,x

>). But keep in mind that oﬃcially, all partial

recursive functions are unary.

We also overload the symbol <>by deﬁning the following pairing op-

erator on functions:

<f,g>

def

= λx.<f (x),g(x)>.

Basic Closure Properties

The partial recursive functions contain the constant functions κ

def

= λx.c

and projections π

, π

and are closed under composition and pairing

(among other closure properties). That is, if f and g are partial recursive

functions, then so are f ◦ g

def

= λx.f(g(x)) and <f,g>

def

= λx.<f (x),g(x)>.

The constant functions and projections are total. The composition f ◦g

is deﬁned on x iﬀ g is deﬁned on x and f is deﬁned on g(x). The pair <f,g>

is deﬁned on x iﬀ both f and g are deﬁned on x.