keerukusteooria
Keerukusteooria on teoreetilise arvutusteaduse haru, mis uurib, kui palju ressursse – peamiselt aega ja mälu – on vaja lahendada erinevaid arvutusprobleeme ning kuidas nende nõudmised kasvavad sisendi suurusega. Eesmärk on mõista, millised probleemid on lahendatavad efektiivselt ning millal lahendamine muutub praktiliselt võimatuks, ning kirjeldada raskusklasside hierarhiat ja nende piiranguid.
Peamised mõisted hõlmavad P- ja NP-klassi. P sisaldab probleeme, mida saab lahendada polünomiaalse ajaga deterministilise algoritmiga.
Lisaks uuritakse probabilistilise ja kvantkeerukuse klasside vahelisi suhteid. Tüüpilised probabilistilise keerukuse klassid on BPP, RP ja
Keerukusteooria annab teoreetilise raamistiku algoritmide ja nende piiride hindamiseks, mõjutab krüptograafiat ja tarkvaratõendust ning pakub aluse