Portál:Matematika/Odporúčaný článok/46 2006

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.

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.