Teória zložitosti

Z Wikipédie

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.

Obsah

1 Prehľad
2 Rozhodovacie problémy
3 Často používané triedy zložitosti
4 Problém P=NP
5 Významní vedci v oblasti teórie zložitosti
6 Externé odkazy

[úprava] 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(n²)	$Ω$ (n²)
Rýchle triedenie (Quick Sort)	O(nlogn)	O(n logn)	$Ω$ (n²)
Triedenie haldou (Heap Sort)	O(n logn)	O(n logn)	$Ω$ (n logn)
Triedenie zlučovaním (Merge Sort)	O(n logn)	O(n logn)	$Ω$ (n logn)

[úprava] 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šnie), 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ť.

[úprava] Č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.

[úprava] Problém P=NP

Triviálne platí inklúzia $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 naviac $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 efeketívne riešenie pre celú triedu NP (vďaka polynomiálnej transformovateľnosti).