Skaičiavimo sudėtingumo teorija yra matematikos ir informatikos sritis, susijusi su ištekliais, reikalingais kompiuterinės sistemos problemoms spręsti. Yra keletas būdų, kaip nustatyti problemos išteklių poreikius. Kai kurios problemos gali būti neįgyvendinamos esamose kompiuterių sistemose dėl jų išteklių poreikio. Tyrėjai klasifikuoja problemas pagal sunkumą ir gali suskirstyti skaičiavimus į daugianario (P) ir neterministinio polinomo (NP) problemas.
Skaičiavimui reikia išteklių, tokių kaip laikas, saugykla ir aparatinė įranga. Kompiuterinė sistema gali turėti apribojimų, dėl kurių problemos funkciškai neįmanoma išspręsti, nes ji neturi turimų išteklių. Tobulėjant kompiuterinėms technologijoms, anksčiau neišspręsta problema gali tapti išspręsta pasitelkus naujas technologijas ir tyrimus skaičiavimo sudėtingumo teorijos srityje. Problemos išsprendžiamumą lemia ne jos sudėtingumas, o algoritmai, naudojami jai išspręsti.
Skaičiavimo sudėtingumo teorijoje P problema yra ta, kurią galima išspręsti daugianario laiku naudojant paprastą algoritmą. Tam vis tiek gali prireikti didelių išteklių, tačiau jį galima išspręsti ir patikrinti kompiuteriu. Tokios problemos gali būti greitai išsprendžiamos tol, kol kompiuteris turi turimų išteklių reikiamiems skaičiavimams atlikti.
NP problemos yra sudėtingesnės. Neįmanoma taikyti vieno algoritmo, todėl gali prireikti naudoti sudėtingesnes parinktis, pvz., lygiagrečias Tiuringo mašinas, kurios gali ištirti kelias parinktis. Problema gali būti išspręsta tokiu būdu, tačiau tam reikės daug daugiau išteklių. Tokios problemos gali būti lengvesnės žmonėms, turintiems pažangų loginį mąstymą, nes lūžio taškas dažnai yra loginis, o ne vien skaičiavimo sunkumai. Keliaujančio pardavėjo problema, kurios tikslas yra rasti efektyviausią maršrutą tarp kelių maršruto miestų, yra klasikinis NP problemos pavyzdys skaičiavimo sudėtingumo teorijoje.
P ir NP problemų klasifikavimas pagal skaičiavimo sudėtingumo teoriją gali būti sudėtingas uždavinys, o problemos gali kilti pirmyn ir atgal visoje takoskyroje. Nedidelis skaičiavimo uždavinių rinkinys netinka nė vienai kategorijai ir kartais priskiriamas nei vienai, nei kitai, kad tai atspindėtų. Galų gale gali būti įmanoma sukurti algoritmą NP problemai išspręsti, o kai kuriais atvejais jis gali būti taikomas kitoms panašios struktūros problemoms. Tačiau kituose atveju tai gali būti specifinė problema. Tokių programų tyrinėjimo ir jų sprendimo būdų kūrimo procesas yra svarbi matematikos ir informatikos sritis, prisidedanti prie pažangių, galingų kompiuterių sistemų kūrimo.