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.

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 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 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).