keerukusteooriat

Keerukusteooria on teoreetilise arvutiteaduse osa, mis uurib, kui palju ressursse – eelkõige aega ja mälu – on vaja erinevate arvutusprobleemide lahendamiseks. Selle peamine eesmärk on määratleda probleemide lahendamise raskus ning kirjeldada, kuidas raskus kasvab sisendi suurusega. Teooria hindab, millal probleem on teostatav mõistlike piiridega ning milliseid ressursse on vaja selle lahendamiseks.

Peamised mõisted hõlmavad keerukusklasse, reduktsioone ja täiuslikkust. Klassis P lahendatakse probleemid polynoomaalse ajaga. Klass NP hõlmab probleeme, mille lahendused saab kontrollida polynoomaalse ajaga, kui lahendus on esitatud. NP-täielikud probleemid on NP-s kõige raskemad; näide on SAT. Reduktsioonid võimaldavad võrrelda raskust erinevate probleemide vahel ja näidata, kui ühe probleemi lahendus saab teisendada teiseks probleemiks, säilitades raskusastme.

Olulised tulemused hõlmavad Cook–Levin teoreemi, mis näitab, et SAT on NP-täielik; Time ja Space Hierarhia teoreemid, mis näitavad, et lisanduv ajalai või ruum suurendab lahendamiseks võimalikke probleeme; ning Savitchi teoreem, mis seob nondeterministliku ja deterministliku ruumi. Keerukusteooria annab mõistmise arvutuse piiridest, mõjutab krüptograafiat ja algoritmide disaini ning aitab hinnata, millised probleemid väärivad püsiva uurimise või praktilisi heuristikaid.

Ajalugu: teadmised kutsusid alguse 1960–1970. aastatel Stephen Cooki ja Leonid Levini tööst; aluseks olid teooriad ja määratlused, mis tõstsid esile NP-täielikkuse ja keerukuse hierarhiad.