CS计算机代考程序代写 algorithm Limits of

Limits of
Computation
13 – Complexity Classes Bernhard Reus
1
The complexity story so far
• time measure for machine like languages • and for WHILE
• discussed fairness
• comparing timed programming languages
2

THIS TIME
•
• •
•
Time Complexity
We deal with worst case time complexity, so we need
upper bounds of runtime (as a function)
Define complexity classes for programs (asymptotic time complexity)
image: mindhacks.com/blog
from which we derive complexity classes for problems.
3
Runtime Bounds:
functions describing worst-case complexity
4

Fig. 13.1 several functions are plotted that describe such time bou r
m a
o
m )
– d
n m
f
u a
W i
l e m
n r
o
have a small degree. The degree of the time bound corresponds often to the depth
.×
the above, we are interested in the behaviour when we move (far) The time needed is supposed to increase, the question is by how ime bounds
• •
This is the set of programs that have a runtime th
input,
p
Figure 13.1 highlights that logarithmic and linear t nential ones rather bad. In the following, recall that w data value d ∈ L-data. Recall also that we have defin
Runtime Bounds
in Definition 3.2.
• A runtime bound is a total function on the natural numbers: 
Definition 13.1 (programs with bounds) Given a ti • andatotalfunction f :N→N,wedefinefour
which maps the size of the input of a program to the time
programs:
it takes at most to run the program with the respective
1 . L t i m e ( f ) =􏰦{ p ∈ L – p r o g r a m s | t i m e L ( d ) ≤ f ( | d | )
such that for all inputs the program’s runtime is bounded by 2. Lptime = Ltime(p(n))
the runtime bound (worst case).
p is a polynomial
This set is the union of all set of L programs tha
The time bound f is a function on natural numbers, as it
must deapsentidmoenbsoizuenodf.pRroegcramll tinhpauttadp.olynomial function
if d is a binary tree then its size, | d |, is the number of leaves, i.e. of nils in the tree ck ×nk +ck−1 ×nk−1 +···+c2
3. Llintime = 􏰦 Ltime(k×n) 13.1 Runtime Bounds k≥0
e abbreviate ed this functi
med progra classes (sets
for all d ∈ L at is bounde
t have a poly is of the for
×k2 +c1 ×k 163
4. Lexptime
Ltime(2p(n))
5
This set is the union of all set of L programs that have a linear bound. Linear functions are of the form f (n) = k × n.
= 􏰦k≥0
Where p(n) is a polynomial. This set is the unio
400
200
have an exponential function f as time bound. E
form f (n) = 2p(n) so we allow not only n in the Runtime Bound Examples
13.1 Runtime Bounds n as well. 163
Asymptotic time
200In this chapter we focus on polynomial time. Why do complexity means that we
400
will be mainly interested
exponential time bounds for algorithms? And what
Let us have a closer look at the growth of linea
functions. Assume that you have various algorithm
0in the unit cost measure is in real time 10−9 s. Co
(what the result of the time bound functions is) if w 00210203…30n40 n
in the runtime bound’s behaviour for large input,
i.e. what happens in the limit!
=n
1onlGiner)aph of log x (magenta), x (green), x2 (blue), 2x (red), 3x (yellow) (Color
n) = 2
, f(n)=2 and f(n)=3 . large size
n, 2
f(n)
Fig. 13.1 Graph of log x (magenta), x (green), x2 (blue), 2x (red), 3x (yellow) (Color figure
Table 13.1
size=n
10
Growth of various time bounds
f (
20
30
40
0
10
1This is of course sufficient since we are interested in runtim
0.01 0.1 0.01 ms 1 μs 59 μs .1 Growth of various time bounds
n(μs) n2 (μs) n3 2n 3n
Fig. 13.
online)
Table 13 30
50
n of all set o
xponential f exponent but
we do this? about linear t r, polynomia
s for a probl nsider how
e consider fu
Table13.1 f figure
e of decision pr
size=n
10
30 50
2
n (μs)
n
0.03 0.9 0.05 2.5
24.3 ms 0.31s
1 s 13da3ys
2.4 days
2.3×105 centunries 2
n(μs)
n
6
3
59 μs
2.4 days
23 10 centuries
time bound0e.x0p1ressed in the corr0es.p1onding “real time”0(.i0ns1teamd osf natural nu1mμbesrs) to convey a better feeling for the large numbers involved.2
0.03 0.9 24.3 ms 1 s We have only used polynomials with small exponents. But this is somewhat justifi-
able as for most known (useful) algorithms with polynomial runtime, the polynomials 0.05 2.5 0.31s 13days
5

Classifying Programs by Runtime
13.1. RUNTIME BOUNDS CHAPTER 13. COMPLEXITY CLASSES
with a time bound f are necessarily always terminating1. We are interested in worst- case comAplreexiatydwyedciosncsuidsesreudpp“errobbounsdtns.ess” w.r.t computability
Since we only look at asymptotic time complexity we are interested in how the (Church-Turing thesis)
•
time bound (and thus the time needed at most by a program) grows when the input
• now with resource-bounds = time bound for running time
grows. In Fig. 13.1 several functions are plotted (quadratic in blue, exponential in
•
red, linear in olive green) that describe such time bounds. According to the above,
classify sets of programs that run within the same time
we are interested in the behaviour when we move (far) right on the x-axis. The time bound
needed is supposed to increase, the question is by how much?
• distinguish four classes of programs 
* those with a given function as time bound,  
* those with all polynomial, linear, and exponential functions, 
162 respectively, as time bounds.  13 Complexity Classes 400
13.1 Runtime Bounds
Runtime bounds are total functions from natural numbers to natural numbers. They
describe the time (i.e. number of time units) a program may take at most for a specific
200
Since we only look at asymptotic time complexity we observe how the time bound (and thus the time needed at most by a program) grows when the input grows. In
input in terms of the size of the input. Note that ⊥ 􏰲 n for any n, so programs with a time bound f are necessarily always terminating.1 As we are interested in worst-case complexity, we consider upper bounds.
7
0
Fig. 13.1 several functions are plotted that describe such time bounds. According to 0 10 20 30 40
the above, we are interested in the behaviour when we move (far) right on the x -axis. The time needed is supposed to increase, the question is by how much?
Programs with Bounds
2xx
Figure 13.1 highlights that logarithmic and linear time bounds are good and expo-
Fig.13.1:Graphoflog2x(magenta),x(green),x (blue),2 (red),2 (yellow) nential ones rather bad. In the following, recall that we abbreviate by |d| the size of a
data value d ∈ L-data. Recall also that we have defined this function for D explicitly In the following, recall that we abbreviate by |d| the size of a data value d 2 L-
in Definition 3.2.
data. Recall also that we have defined this function for D explicitly in Def. 3.2. Definition 13.1 (programs with bounds) Given a timed programming language L
Danedfinaitiotnal1f3u.1nc(tpiornogrfam:sNw→ithNbo,uwnedsd)e.fiGnievefnouartcimlaesdsepsr(osgertasm)omfintigmleanbgouangdeed Lproagnrdaamsto:talfunctionf:N!N,wedefinefourclasizseosfi(nspeuts)oftimebounded
programs: L
1 . L t i m e ( f ) =􏰦{ p ∈ L – p r o g r a m s | t i m e p ( d ) ≤ f ( | d | ) f o r a l l d ∈ L – d a t a }
time( f ) L 1.LThisis=the{spet2oLf-programst|htaimthea(vde)arufn(t|idm|)eftohratalilsdbo2uLn-ddeadtab}yfunction f.
as time bound. Recall that a polynomial function is of the form
p
2. Lptime =S Ltime(p(n)) Thisistheseptisoafppolryongomraiamlsthathaveafurnuctniotnimsweiththinaptutisnabnoduonutdpeutdp(bny)functionf.
Tphtimise set is the union of atilmles(ep(tno))f L programs that have a polynomial function p 2.L = pisapolynomialL
This set is the union of all set of L programs that have a polynomial function p as time bound. Recall that a polynomial function is of the form
ck ×nk +ck−1 ×nk−1 +···+c2 ×k2 +c1 ×k+c0. S􏰦 ck ⇥nk +ck1 ⇥nk1 +···+c2 ⇥n2 +c1 ⇥n+c0 .
3. Llintime = k≥0 Ltime(k×n)
lintime time(k⇥n)
3. LThis se=t is the uLnion of all set of L programs that have a linear function f as time
k0
bound. Linear functions are of the form f (n) = k × n.
1 􏰦p(n)
Thiseixsptoimf ecourse sufficietnimt es(i2nce )we are interested in runtime of decision procedures.
4.L = k≥0L 8
Where p(n) is a polynomial. This set is the union of all set of L programs that
have an exponential function f as time bound. Exponential functions are of the
form f (n) = 2 n as well.
p(n) 168
so we allow not only n in the exponent but any polynomial of

Definition 13.1 (programs with bounds) Given a timed programming language L
Deafinndiatiotontalofupnrctoiognrafm:sNwi→thbNo,uwneddsefiGnievefnouartcilmasesdesp(rsoegtsr)amofmtimngelbaonugnudaegde L apnrdogaratomtsa:l function f : N ! N, we define three sets of time bounded programs
time( f ) L 1.Ltime(f)={p∈L-programs|timep(d)L≤ f(|d|)foralld∈L-data}
1. L = {p2L-programs | timep(d)  f(|d|) for alld2L-data }
This is th􏰦e set of programs that have a runtime that is bounded by function f . This is the set of programs that have a runtime that is bounded by function
2. Lptime = p is a polynomial Ltime( p(n)) f.
This set isSthe union of all set of L programs that have a polynomial function p aspttiimee bound. Recall that a ptoimlyen(po(mn)i)al function is of the form
2. L = p is a polynomialL
Programs with Bounds (II)
This set is the union of all set of L programs that have a polynomial ck ×nk +ck−1 ×nk−1 +···+c2 ×k2 +c1 ×k+c0.
function p as time bound. Recall that a polynomial function is of the
formf(n􏰦)S=c ⇥nk+c ⇥nk1+⇥+c ⇥n2+c ⇥n+c. lintime k time(k×n) k1 2 1 0
3.L = k≥0L
Tlhinistimseet is the uniontimofe(akll⇥snet)tsoffLprograms that have a linear function f as time 3.L = L
􏰦 k0
bound. Linear functions are of the form f (n) = k × n.
This set is the union
o
f all set of L programs that have a linear function 4. Lexptime = k≥0 Ltime(2 )
p(n
f as time bound. As linear functions are of the form f(n) = k · n.
)
Where p(n) is a polynomial. This set is the union of all set of L programs that
S p(n)
heaxvpetiamneexponential function ftiamset(i2me b)ound. Exponential functions are of the
4. L = p is a polynomialL
form f (n) = 2p(n) so we allow not only n in the exponent but any polynomial of This set is the union of all set of L programs that have an exponential n as well.
function f as time bound. An exponential functions are of the form f(n) =
In this chapter we focus on polynomial time. Why do we do this? Why don’t we like
2p(n) where p is polynomial.
exponential time bounds for algorithms? And what about linear time?
Why do we focus on linear time and polynomial time? Why don’t we like
Let us have a closer look at the growth of linear, polynomial, and exponential
xponential time bounds for algorithms?
functions. Assume that you have various algorithms for a problem and that a unit
−9
Let us have a closer look at the growth of linear, polynomial, and exponential
in the unit cost measure is in real time 10
s. Consider how much time it takes
unctions. Assume that you have various algorithms for a problem and that a
(what the result of the time bound functions is) if we consider functions f (n) = n,
23nn
9
e f
unit in the unit cost measure is in “real time” 10 seconds. Consider how much f(n)=n , f(n)=n , f(n)=2 and f(n)=3 .Table13.1from[2]showsthe
time it takes (what the result of the time bound functions is) if we consider functions f(n) = n, f(n) = n2, f(n) = n3, f(n) = 2n and f(n) = 3n. The
1This is of course sufficient since we are interested in runtime of decision procedures.
9
8
From Classes of Programs to
Classes of Problems
10

Fix L-data
• To be able to compare different machine models (notions of computability) we fix the data type of programs (i.e. programming languages):
• L-data = {0,1}* i.e. words made up of 0 and 1’s,  
e.g. 11011, 00001100 . For instance, we can encode {0,1}* in WHILE-data (binary trees), as lists of 0s and 1s;
• ‘Problems’ are sets (properties) of such words. 1101 = [1,1,0,1] • The size of such words is the length, e.g. | 1101 | = 4
164 13 Complexity Classes 164 11 13 Complexity Classes
Let us simply take the words over alphabet {0,1} as this domain, i.e. {0,1}∗. In a Let us simply take the words over alphabet {0,1} as this domain, i.e. {0,1}∗. In a
way they correspond to words of bits which is how information is stored on modern
way they correspond to words of bits which is how information is stored on modern devices anyway. It is also clear that Turing machines take such words as inputs
devices anyway. It is also clear that Turing machines take such words as inputs (restricting the alphabet accordingly). In languages with binary tree type D we need
(restricting the alphabet accordingly). In languages with binary tree type D we need
to encode those words as lists of 􏰯0􏰰 and 􏰯1􏰰 which is not a problem. The word 010
]or system as natural numbers.
to encode those words as lists of 􏰯0􏰰 and 􏰯1􏰰 which is not a problem. The word 010 corresponds then to the list [ 0, 1, 0 ] or [ nil, [nil, nil], nil ]. For register machines we
ature.3 ature.3
me
Prot [ 0blem Classes
[ nil, [n
],
].F
corresponds then to
can interpret lists of 0 and 1 as binary numbers and represent them in the decimal
,1,
can interpret lists of 0 and 1 as binary numbers and represent them in the decimal
0
il, nil
Below we define time complexity classes for problems. We use boldface short
system as natural numbers.
Below we defin
x
o
the
lis
nil
or
reg
e ti
com
ple
ity
abbreviations to denote complexity classes of problems as it is standard in the liter-
classes
abbreviations to denote complexity classes of problems as it is standard in the liter-
Definition13.2 (complexityclasses)GivenatimedprogramminglanguageLanda Definition13.2 (complexityclasses)GivenatimedprogramminglanguageLanda
total function f : N → N, we define four (complexity) classes of problems: total function f : N → N, we define four (complexity) classes of problems: 1. The class of problems L-decidable in time f is:
1. The claLss of problems L-d∗ecidable in time f is: time( f )
TIME (f)={A⊆{0,1} |Aisdecidedbysomep∈L } TIMEL( f ) = {A ⊆{0, 1}∗ | A is decided by some p ∈ Ltime( f )}
In other words, this is the class of all problems (or sets) A about words over In other words, this is the class of all problems (or sets) A about words over
alphabet {0, 1} that are decided by an L-program with a runtime that is bounded alphabet {0, 1} that are decided by an L-program with a runtime that is bounded
by time bound (function) f . by time bouLnd (function) f .
2. TheclassPLofproblemsL-decidableinpolynomialtimeis: 2. TLhe class P of pr∗oblems L-decidable in polynomptimael time is:
P ={A⊆{0,1} |Aisdecidedbysomep∈L } PL = {A ⊆{0,1}∗ | A is decided by some p ∈Lptime}
In other words, this is the class of all problems (or sets) A about words over In other words, this is the class of all problems (or sets) A about words over
alphabet {0, 1} that are decided by an L-program with a runtime that is bounded alphabet {0, 1} that are decided by an L-program with a runtime that is bounded
by a polynomial. by a polynomiLal.
3. TheclassLINLofproblemsL-decidableinlineartimeis: 3. TheLclass LIN of pr∗oblemsL-decidable in linear tilimntiemeis:
LIN ={A⊆{0,1} |Aisdecidedbysomep∈L }
LINL = {A ⊆{0,1}∗ | A is decided by some p ∈Llintime}
In other words, this is the class of all problems (or sets) A about words over
for pr
ble
ms
.W
eu
ister machines we
se boldface short
In other words, this is the class of all problems (or sets) A about words over alphabet {0, 1} that are decided by an L-program with a runtime that is bounded
alphabet {0, 1} that are decided by an L-program with a runtime that is bounded by a linear function.
by a linear funcLtion.
4. TheclassEXPLofproblemsL-decidableinexponentialtimeis:
4. The cLlass EXP of pr∗oblems L-decidable in exponenextpiatiml etime is: EXP ={A⊆{0,1} |Aisdecidedbysomep∈L }
12
EXPL = {A ⊆{0, 1}∗ | A is decided by some p ∈ Lexptime}
In other words, this is the class of all problems (or sets) A about words over
In other words, this is the class of all problems (or sets) A about words over
alphabet {0, 1} that are decided by an L-program with a runtime that is bounded

Dtoetfialnfiutinocnti1on3.2f :(cNom→plNex,itwyecldaesfisnese)fGouivre(ncoamtipmlexditpyr)ocglraasmsemsionfgplraonbgleumagse:Landa
total function f : N → N, we define four (complexity) classes of problems: 1. The class of problems L-decidable in time f is:
L ∗ time(f) 1. ThIeMcElas(sfo)f=pro{bAle⊆ms{0L,-1d}ec|idAabislediencitdimedebfyiso:me p ∈L }
L ∗ time(f)
TInIMotEher( wf )o=rds{,Ath⊆is {i0s,t1h}e c|laAssisodfeaclildepdrobylesmosm(eorp s∈etLs) A ab}out words over
Ianlpohtahbeert w{0o,r1d}s,ththatisaries dtheecidcleadssbyofanalLl -probglreamsw(oitrh saetrsu)ntAimaebtohuatt wisobrodusnodveedr ablyphtiambetb{o0u,n1d} (thfuant catrieond)ecfi.ded by an L-program with a runtime that is bounded
L
2. bTyhetimcleasbsoPundof(fpurnocbtlieomn)s Lf .-decidable in polynomial time is:
L L ∗ ptime
2. TPhe=cla{sAs⊆P {0o,f1p}rob|lAemisdLe-cdiedceidabbylesoimnepoply∈noLmial}timeis:
Problem Classes (II)
L ∗ ptime
PIn o=th{eAr w⊆o{r0d,s,1}thi|s Aisitshdeecliadsesdobfyaslolmpreobple∈mLs (or}sets) A about words over
alphabet {0, 1} that are decided by an L-program with a runtime that is bounded In other words, this is the class of all problems (or sets) A about words over
by a polynomial.
alphabet {0, 1} that are decided by an L-program with a runtime that is bounded
3. TheclassLINLofproblemsL-decidableinlineartimeis: by a polynomial.
LINL = {A ⊆{0,1}∗ | A is decided by some p ∈Llintime} 3. TheclassLINLofproblemsL-decidableinlineartimeis:
In other words, this is the class of all problems (or sets) A about words over LINL = {A ⊆{0,1}∗ | A is decided by some p ∈Llintime}
alphabet {0, 1} that are decided by an L-program with a runtime that is bounded In other words, this is the class of all problems (or sets) A about words over
by a linear function.
alphabet {0, 1} that are decided by an L-program with a runtime that is bounded
4. TheclassEXPLofproblemsL-decidableinexponentialtimeis: by a linear function.
EXPL = {A ⊆{0, 1}∗ | A is decided by some p ∈ Lexptime}
4. TheclassEXPLofproblemsL-decidableinexponentialtimeis:
In other words, this is the class of all problems (or sets) A about words over EXPL = {A ⊆{0, 1}∗ | A is decided by some p ∈ Lexptime}
alphabet {0, 1} that are decided by an L-program with a runtime that is bounded In other words, this is the class of all problems (or sets) A about words over
by an exponential function.
alphabet {0, 1} that are decided by an L-program with a runtime that is bounded
by an exponential function.
We often drop the superscript indicating the language in question and simply use
LIN, P, or EXP if we implicitly understand which programming language we are We often drop the superscript indicating the language in question and simply use
13.2 Time Complexity Classes 165
referring to.
LIN, P, or EXP if we implicitly understand which programming language we are
referring to.
Another justification to drop the superscript would be if we were allowed not
Proposition13.1 Foranynotionof“effectiveprocedure”L,itholdsthat
to care which programming language we use. In the next section we will justify Another justification to drop the superscript would be if we were allowed not
13 L
exactly that. We will look at the “roLbustnLess” of thLe class P, i.e. how P relate for to care which programming language we use. In the next section we will justify
LIN ⊆P ⊆EXP
different languages L, and we will meet yet another thesis that is similar to the
exactly that. We will look at the “robustness” of the class P, i.e. how PL relate for Church–Turing Thesis.
different languages L, and we will meet yet another thesis that is similar to the
From Definition 13.2 it follows immediately for a fixed language L: Church–Turing Thesis.
13.3 Lifting Simulation Properties to Complexity Classes
From Definition 13.2 it follows immediately for a fixed language L:
3In [1] the classes are called PTIME, LINTIME, NPTIME (there is no EXPTIME), respectively.
Proposition 13.1 tells us the simple relationship between complexity classes of prob-
3
to establish relationships between complexity classes that use different kinds of effec-
In [1] the classes are called PTIME, LINTIME, NPTIME (there is no EXPTIME), respectively. lems decided using the same language or notion of computation. Next, we would like
L
and lift them straightforwardly to relations between complexity classes.
Lemma 13.1 L ≼lintime M implies LINL ⊆ LINM, and as a consequence, L ≡lintime M implies LINL = LINM.
This means that if L can be simulated by M up to linear time difference then every problem in LINL is already in LINM. And then, as a consequence, that if L and M are linearly equivalent then LINL and LINM are the same.
i
f
s
t
e
iv
t
e
p
i
n
r
oce
g
S
dur
es.
I
t tur
i
m
u
ns
o
l
a
ut
w
t
i
o
e
ca
n
P
n use
th
r
e
sim
Proof Let us prove this (as it is not difficult): Assume that we have a problem Proof in exercises.
A ∈ LINL. This means there is some L-program that decides A in linear time, the
latter means more precisely that timeLp (d ) ≤ c × |d | for some constant c ≥ 0 and all
d ∈ D. By definition L ≼lintime M implies that there exists an M-program q such that SiMmilar rLesults can be shown for P
􏰖q􏰗 = 􏰖p􏰗 , and program q is at most a linear factor slower than p, in other (more precise) words: timeqM(d) ≤ ap × timeLp(d) for some (program dependent) ap ≥ 0 and all data d ∈ D.
Now combining those two results about the runtime of q we get for all d that:
ML
o
p
ula
e
tio
r
t
n
re
i
e
la
tio
s
t
ns
fro
o
C
mD
efin
l
a
i
tio
s
n1
s
2
.6
timeq ≤ap ×timep(d)≤ap ×c×|d| 14
From this follows (as ≤ is an order, in particular transitive) t i m e qM ≤ ( a p × c ) × | d |

Related Posts