IB107 Vyčíslitelnost a složitost
časová složitost algoritmu, časové složitostní třídy
Jan Strejček
Fakulta informatiky Masarykova univerzita
vztah teorie vyčíslitelnosti a teorie složitosti
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
2/21
časová složitost algoritmu
■ počet "kroků" výpočtu
■ závisí na vstupu a výpočetním modelu
■ jako základní model použijeme Turingův stroj
■ zkoumáme nejhorší případ, tedy maximální počet kroků v závislosti na délce vstupu
■ lze zkoumat i průměrný případ
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
3/21
časová složitost deterministického Turingova stroje
Definice (časová složitost TM)
Necht M je úplný deterministický (jednopáskový nebo vícepáskový) Turingův stroj se vstupní abecedou Z. Pro každé i^gF definujeme ím(w) jäko počet kroků výpočtu stroje M na vstupu w. Časová složitost stroje M je pak funkce TM : N    N definovaná vztahem
TM(n) = max{ŕM(i/i/) | w e Z"}.
Říkáme, že M pracuje v čase TM(ri).
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
4/21
příklad
M = {{q0, q^, qacc, qrej}, {0,1}, {0,1, >, u}, >, u, S, q0, qacc, qrej)
s	>	0	1		u	
qo	(qo, >, R)	(Qo,0,fí)	(Qi, 1,		{qacc, ~,	")
q^		(Qrej, ~, -)			(qacc, —,	")
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
5/21
příklad
M = ({qo,   , r, s0, s^, qacc, qrej}, {0,1}, {0,1, X, >, u}, >, U, S, q0, qacc, qrej)
s	>	0	1	X	u
		(qb,0,fí)	(<7i,1,fl)		(r,u,L)
q^		{Qrej, - -)	(<7i,1,fl)		(r,u,L)
r	(So, >, R)		(/", 1,	(r, X, L)	
So		(si, X, fí)	(qfrey,-,-)	(sq,X, R)	{Qacc, ~) —)
s^		(si,0,fí)	(/", X, L)	(si, X, fl)	(<7rey, -, -)
o
o
o
1
1
1
u
u
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
6/21
motivace pro asymptotickou analýzu
■ jaká složitost je lepší: 6n nebo n2 + 5?
■ na delších vstupech jsou výpočty obvykle delší
■ zajímá nás chování pro n -> oc
■ konstantní faktor neuvažujeme (výpočet lze zrychlit)
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy 7/21
věta o zrychlení
Pro každý deterministický úplný TM M a pro každé m > 1 lze zkonstruovat deterministický úplný TM M' tak, že L(M) = L(M') a
-r     í   \ /  ^MÍn)   .   _ , A
Důkaz:
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
8/21
(9-notace
Definice (asymptotická horní závora)
Necht ŕ, g : N    IR+ /sol/ funkce. Řekneme, že g je asymptotická horní závora pro f, a píšeme f e O (g) nebo f = O (g), jestliže existují konstanty c,í)0gN takové, že pro každé n> n0 platí
f{n) < c-g{rí).
Příklad: 15n3 + 3n2 + 11 n + 7
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
9/21
počítání s (9-notací
■ logaritmy: O(logn)
■ sčítání: 0(n3) + O(n)
■ mocniny: 2°^
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
10/21
příklad
TM M rozhodující {0^1 ^ | k > 0} lze popsat i takto:
□ Zjistí, zda vstup obsahuje nějakou 0 za 1. Pokud ano, zamítne.
B Dokud je na pásce nějaká 0, projíždí pásku a vždy škrtne jednu 0 a jednu 1. Pokud se nepovede k nějaké 0 najít 1, zamítne.
B Pokud po vyškrtání všech 0 zbude na pásce nějaká 1, zamítne. Jinak akceptuje.
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
11/21
deterministické časové složitostní třídy problémů
časová složitost problému = nejmenší časová složitost, s jakou lze daný problém rozhodnout
Definice (časová složitostní třída problémů)
Každá funkce f: N -s> M+ definuje (deterministickou) časovou složitostní třídu problémů
TIME(f(n)) = {L\Lje rozhodovaný nějakým deterministickým
jedno- nebo vícepáskovým TM M s časovou složitostí TM{n) = 0(f(n))}.
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
12/21
příklad
L = {Okj\k \k>0}
■ ukázali jsme jednopáskový det. TM rozhodující L v čase 0(n2)
■ existuje jednopáskový det. TM rozhodující L v čase 0(n\og n)
D Zjistí, zda vstup obsahuje nějakou 0 za 1. Pokud ano, zamítne.
B Dokud páska obsahuje nějakou 0 i 1, opakuje následující: Pokud je celkový počet 0 a 1 n pásce lichý, zamítne. Pokud je sudý, škrtne každý lichý výskyt 0 a každý lichý výskyt 1.
Q Jestliže na pásce zůstane nějaká 0 nebo 1, zamítne. Jinak akceptuje.
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
13/21
příklad
L = {Okj\k \k>0}
■ neexistuje jednopáskový det. TM rozhodující L s menší složitostí než 0(n log n)
(platí, že každý jazyk rozhodnutelný jednopáskovým det. TM v čase o(nlogn) je regulární)
■ existuje dvoupáskový deterministický TM rozhodující L v čase O(n), tedy L je ve třídě TIME(n)
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
14/21
vliv výpočetního modelu
■ na rozdíl od vyčíslitelnosti, ve složitosti na výpočetním modelu zaleží
■ rozdíl je i mezi jednopáskovým a dvoupáskovým deterministickým TM
■ jaký model zvolit?
■ je volba deterministického vícepáskového TM správná?
■ rozdíly jsou u běžných sekvenčních deterministických výpočetních modelů poměrně malé
■ např. RAM (random-access machine) pracující v čase f(n) lze převést na vícepáskový deterministický TM pracující v čase 0(f3(n) • (f(n) + n)2)
■ nedeterminismus přináší výrazný rozdíl
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
15/21
převod vícepáskového TM na jednopáskový
Věta
Pro každý vícepáskový deterministický TM pracující v čase f(n)> n lze sestrojit ekvivalentní jednopáskový deterministický TM pracující v čase O(f2(n)).
Důkaz:
D neprázdný obsah k pásek a polohy hlav zapíšeme za sebe na 1
pásku O(n) B simulace jednoho kroku
■ zjistit informace pod hlavami = projít pásku,
každá původní páska má max. f (n) neprázdných polí O (f (n)) m provést krok, zapsat nové symboly a posunout hlavy (případně přidat další políčka na původní pásky
odsunutím obsahu dalších pásek, max. k políček) 0(f(ri))
B simulujeme f(n) kroků      -> celkem O(n) + 0(f2(n)) ■
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy 16/21
časová složitost nedeterministického Turingova stroje
Definice (časová složitost nedeterministického TM)
Necht M je úplný nedeterministický Turingův stroj se vstupní abecedou Z. Pro každé i^Gľ definujeme (m(w) jako počet kroků nejdelšího výpočtu stroje M na vstupu w. Časová složitost stroje M je pak funkce TM : N    N definovaná vztahem
TM(n) = max{ŕM(i/i/) | w e Z"}.
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
17/21
nedeterministické časové složitostní třídy problémů
Definice (nedeterministická časová složitostní třída problémů)
Každá funkce f: N -> IR+ definuje (nedeterministickou) časovou složitostní třídu problémů
NTIME(f(n)) = {L\Lje rozhodovaný nějakým nedeterministickým
jedno- nebo vícepáskovým TM M s časovou složitostí TM(ri) = O (f (n))}.
Z definic plyne TIME(ŕ(n)) c NTIME(ŕ(n)).
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
18/21
převod nedeterministického TM na deterministický
Věta
Pro každý nedeterministický jednopáskový TM pracující v čase f(ri) > n lze sestrojit ekvivalentní deterministický jednopáskový TM pracující v čase 2°^^.
Důkaz: Nedet. TM M, který má z každé konfigurace max. k přechodů, simulujeme 3-páskovým deterministickým strojem, který prohledává strom výpočtů M do šířky. Pro každý uzel provedeme znovu výpočet z iniciální konfigurace.
Strom výpočtů má hloubku nejvýše f(ri) a tudíž má nejvýše kf^ listů a méně než 2 • kfW uz|ů. -> 0(kf^) uzlů
Simulace výpočtu do jednoho uzlu zabere nejvýše 0(f(n)) kroků. 3-páskový stroj tedy pracuje v čase 0(f(n) • kf^) = 2°^f^\
Převod na jednopáskový det. stroj:
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
19/21
nejvýznamnější časové složitostní třídy
deterministické p = PTIME = U/cgntime(n/c)
nedeterministické NP = U/c€NNTIME(^)
EXPTIME = U/cgntime(2 )    NEXPTIME = U/cGNNTIME(2 )
PcNPc EXPTIME c NEXPTIME
■ běžné deterministické sekvenční modely výpočtu lze mezi sebou převádět s polynomiálním nárůstem časové složitosti =4> definice P a EXPTIME nejsou citlivé na volbu modelu
■ EXPTIME je obvykle složitost algoritmů řešících problém hrubou silou
Cook-Karpova teze
P obsahuje právě všechny prakticky řešitelné problémy.
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
20/21
vztah P a N P
P = NP
■ asi nejznámější otevřený problém teoretické informatiky
■ věří se, že platí P c N P
■ důsledky do počítačové bezpečnosti
■ Clay Mathematics Institute (CMI) vypsal 1.000.000 USD za
řešení
IB107 Vyčíslitelnost a složitost: časová složitost algoritmu, časové složitostní třídy
21/21