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
Olulised tulemused hõlmavad Cook–Levin teoreemi, mis näitab, et SAT on NP-täielik; Time ja Space Hierarhia teoreemid,
Ajalugu: teadmised kutsusid alguse 1960–1970. aastatel Stephen Cooki ja Leonid Levini tööst; aluseks olid teooriad ja