Teória zložitosti

Teória zložitosti je časť teoretickej informatiky zaoberajúca sa množstvom požadovaných zdrojov počas výpočtu riešiaceho daný problém. Najčastejšie uvažovaným zdrojom je čas (koľko krokov je potrebných na vyriešenie problému) a priestor (koľko pamäti je potrebnej na vyriešenie problému). Príklady ďalších zdrojov sú počet paralelných procesorov a celková práca vynaložená na riešenie problému v paralelnom systéme. Teória zložitosti sa odlišuje od teórie vypočítateľnosti, ktorá skúma len či sa problém dá vyriešiť alebo nie, bez uvažovania o potrebných zdrojoch.

Prehľad

Po založení teórie objasňujúcej, ktoré problémy sa dajú algoritmicky riešiť a ktoré nie, bolo prirodzené sa pýtať na relatívnu výpočtovú zložitosť vypočítateľných funkcií.

Na problémy sa pozeráme ako na formálne jazyky, a tak jeden "problém" je často celá množina otázok, kde každá otázka je slovo konečnej dĺžky z tohto jazyka. Napríklad, problém FAKTORIZÁCIA je špecifikovaný nasledovne: na vstupe je dané celé číslo zapísané v binárnom tvare, na výstupe požaduje všetky prvočíselné faktory tohto čísla. Jedna takáto otázka (teda konkrétne jedno slovo z jazyka) sa nazýva inštancia problému; napr. "vráť všetky prvočíselné faktory čísla 15" je jedna inštancia problému FAKTORIZÁCIA.

Zložitosť problému väčšinou neudávame pre každú inštanciu zvlášť, ale pre celú triedu inštancií, ktoré majú rovnakú veľkosť problému, čo je väčšinou počet bitov vstupu Turingovho stroja, ktorý problém rieši. Zložitosť je takto vyjadrená ako funkcia závislá od veľkosti vstupu. Pre konkrétnu veľkosť problému nás teda môžu zaujímať viaceré druhy zložitostí: zložitosť najhoršieho prípadu, čo je maximum cez všetky inštancie danej veľkosti, zložitosť najlepšieho prípadu, teda minimum cez všetky inštancie danej veľkosti, či priemerná zložitosť. Nie je zvykom udávať kompletný predpis zložitostnej funkcie, ale len jej asymptotický odhad.

Časová zložitosť problému je počet krokov, ktoré vykoná Turingov stroj pri riešení inštancie problému.

Pamäťová zložitosť problému je maximum z počtu použitých políčok na pracovných páskach Turingovho stroja.

Nasledujúca tabuľka udáva časové zložitosti často používaných algoritmov na triedenie:

Algoritmus	Najlepší prípad	Priemerný prípad	Najhorší prípad
Triedenie priamym vkladaním (Insert Sort)	O(n)	O(n2)	${\displaystyle \Omega }$(n2)
Rýchle triedenie (Quick Sort)	O(n logn)	O(n logn)	${\displaystyle \Omega }$(n2)
Triedenie haldou (Heap Sort)	O(n logn)	O(n logn)	${\displaystyle \Omega }$(n logn)
Triedenie zlučovaním (Merge Sort)	O(n logn)	O(n logn)	${\displaystyle \Omega }$(n logn)

Výpočtová zložitosť má dve základné miery:

• časová zložitosť
• pamäťová zložitosť

Optimalizácia algoritmu sa týka minimalizácie jednej alebo obidvoch mier zložitosti.

Výpočtová zložitosť algoritmu priamo nesúvisí so zložitosťou samotného algoritmu z ľudského pohľadu. Algoritmus môže byť veľmi jednoduchý na pochopenie i implementáciu, napriek tomu môže byť jeho výpočtová zložitosť veľká a naopak.

Druhy výpočtovej zložitosti v závislosti od počtu vstupných prvkov n, (a,b,c sú konštanty, t je čas):

1. lineárna zložitosť: ${\displaystyle t=a.n+b}$
2. logaritmicko lineárna: ${\displaystyle t=a.n.log(n)+b.n+c}$
3. polynomiálna: t je funkciou nejakého polynómu n
4. algoritmy so zložitosťou väčšou než je polynomiálna

Za rýchle algoritmy sa pokladajú prvé tri druhy.

Ilustráciou zložitosti je nasledujúca tabuľka, predpokladajme, že vykonanie jednej operácie trvá jednu mikrosekundu:

Funkcia počtu operácií	20	40	60	80	100	200	500	1000
n	20 µs	40 µs	60 µs	80 µs	100 µs	200 µs	500 µs	1000 µs
n.log n	86 µs	0,2 ms	0,35 ms	0,5 ms	0,7 ms	1,5 ms	4,5 ms	10ms
n2	0,4 ms	1,6 ms	3,6 ms	6,4 ms	10 ms	40 ms	0,25s	1 s
n3	8 ms	64 ms	0,22 ms	0,5 ms	1 s	8 s	125 s	17 min
n4	0,16 s	2,56s	13 s	41 s	100 s	27 min	17 h	11,6 dní
2n	1 s	11,7 dní	36 600 r	3,6.109 r
n!	77 000 r

Z uvedenej tabuľky vidno, že aj keby sme rýchlosť operácii zväčšili 1000x, posledný algoritmus by bol tak či tak neriešiteľný v rozumnom čase a predposledný pre väčšie n tiež.

Tú istú úlohu možno väčšinou riešiť rôznymi algoritmami s rozličnou výpočtovou zložitosťou. Napríklad triedenie sa dá jednoducho implementovať s výpočtovou zložitosťou n², ale existujú aj algoritmy triedenia so zložitosťou n.log n.

Rozhodovacie problémy

Množstvo problémov, ktoré teória zložitosti skúma, je rozhodovacích. Rozhodovací problém je problém, ktorý má booleovskú odpoveď ÁNO/NIE. Napríklad, problém JE-PRVOČÍSLO je nasledovný: na vstupe je dané celé číslo zapísané binárne, na výstup vráť (teda rozhodni) či je prvočíslo alebo nie je. Rozhodovací problém je jazyk. Pre konkrétny problém sa tento jazyk skladá z tých inštancií problému, na ktoré je kladná odpoveď.

Rozhodovacie problémy sa uvažujú veľmi často, pretože každý problém sa dá redukovať na ekvivalentný rozhodovací problém. Napríklad, problém MÁ-FAKTOR je nasledujúci: na vstupe sú celé čísla n a k zapísané binárne, na výstupe požadajume odpoveď, či n má nejaký prvočíselný faktor menší ako k. Je zrejmé, že keď dokážeme vyriešiť problém MÁ-FAKTOR s istými zdrojmi, môžeme vyriešiť celý problém FAKTORIZÁCIA bez zreteľného nárastu zdrojov. Stačí urobiť len binárne vyhľadávanie na k pokiaľ nenájdeme najmenší faktor n. Potom vydelíme vstup týmto faktorom a pokračujeme ďalej, kým ich nenájdeme všetky.

Je potrebné si dať pozor, či skúmame jazyk kladných alebo záporných odpovedí. Ak vieme rozpoznávať jazyk kladných odpovedí (t. j. dávať odpoveď ÁNO) pre nejaký problém s istými zdrojmi, neznamená to, že vieme s takými istými zdrojmi rozpoznávať aj jazyk záporných odpovedí. Napríklad, množinu NP môžeme definovať ako množinu všetkých problémov, ktorých kladné inštancie vieme rozpoznať v nedeterministickom polynomiálnom čase. Naopak, množina Co-NP bude množina problémov, ktorých záporné inštancie vieme rozpoznať v nedeterministickom polynomiálnom čase. Dodnes nevieme, v akom vzťahu tieto triedy sú.

Dôležitý (aj keď možno trochu pesimistický) výsledok teórie zložitosti je fakt, že nech vymyslíme ľubovoľne ťažký problém (t. j. nech vyžaduje ľubovoľne veľa času a pamäti na riešenie), vždy existujú ešte ťažšie problémy. Konkrétne pre časovú zložitosť a triedu rozhodujúcich problémov v polynomiálnom čase tento výsledok hovorí veta o časovej hierarchii. Podobná veta o priestorovej hierarchii sa dá tiež sformulovať.

Často používané triedy zložitosti

Zložitostná trieda P je množina všetkých (rozhodovacích) problémov, ktoré sa dajú riešiť na deterministickom Turingovom stroji v polynomiálnom čase. Táto trieda zodpovedá intuitívnej predstave problémov, ktoré vieme efektívne riešiť.

Zložitostná trieda NP je množina (rozhodovacích) problémov, ktoré sa dajú riešiť na nedeterministických Turingových strojoch v polynomiálnom čase. Do tejto triedy patrí väčšina z nášho pohľadu zložitých problémov, ktoré by sme veľmi radi riešili efektívne, napríklad SAT, problémy hamiltonovských ciest či problém vrcholového pokrytia.

Ďalšie triedy zložitosti.

Problém P=NP

Triviálne platí inklúzia ${\displaystyle P\subseteq NP}$. Otázka, či trieda P je tá istá ako trieda NP (teda či platí rovnosť), je azda najdôležitejšia otvorená otázka informatiky v súčasnosti. Na riešenie problému je vypísaná cena 1 000 000 $.

Otázky ako táto evokujú koncepty ťažkosti a úplnosti. Množina problémov X je ťažká pre triedu problémov Y (X je Y-ťažká), ak každý problém z triedy Y sa dá v polynomiálnom čase transformovať na problém z X. Inými slovami, riešenie problémov v X je aspoň také „ťažké“, ako riešenie (všetkých) problémov z Y. Množina X je úplná pre Y (X je Y-úplná), ak je X je Y-ťažká a navyše ${\displaystyle X\subseteq Y}$. Dodnes sme našli mnoho problémov, ktoré sú (samostatne) NP-úplné (teda každý z nich je NP-ťažký a patrí do NP). Dôvod, prečo ich hľadáme a ďalej študujeme je ten, že podľa tejto definície stačí nájsť efektívne riešenie (teda deterministické v polynomiálnom čase) len pre jeden z nich a tým automaticky máme efektívne riešenie pre celú triedu NP (vďaka polynomiálnej transformovateľnosti).

Významní vedci v oblasti teórie zložitosti

Eric Allender V. Arvind Lazlo Babai Manuel Blum Stephen Cook Lance Fortnow Juris Hartmanis Russell Impagliazzo Richard Karp Leonid Levin Noam Nisan	Christos H. Papadimitriou Alexander Razborov Walter Savitch Alan L. Selman Michael Sipser Richard Stearns Madhu Sudan Salil Vadhan Avi Wigderson Andrew Yao

Externé odkazy

• The Complexity Zoo (anglicky)