Skaitļošanas sarežģītības teorija ir matemātikas un datorzinātnes joma, kas nodarbojas ar resursiem, kas nepieciešami, lai atrisinātu problēmas datorsistēmā. Ir pieejamas vairākas metodes, lai noteiktu problēmas resursu prasības. Dažas problēmas var nebūt iespējamas esošajās datorsistēmās to resursu pieprasījuma dēļ. Pētnieki klasificē problēmas pēc grūtībām un var sadalīt aprēķinus polinoma (P) un neterministiskā polinoma (NP) problēmās.
Aprēķinu risināšanai ir nepieciešami tādi resursi kā laiks, uzglabāšanas vieta un aparatūra. Datorsistēmai var būt ierobežojumi, kas padara problēmu funkcionāli neiespējamu atrisināt, jo tai nav pieejamo resursu. Datortehnoloģijām pilnveidojoties, kāda iepriekš neatrisināma problēma varētu kļūt atrisināma ar jaunu tehnoloģiju palīdzību un pētījumiem skaitļošanas sarežģītības teorijas jomā. Problēmas atrisināmību ne vienmēr nosaka tās sarežģītība, bet gan tās risināšanai izmantotie algoritmi.
Aprēķinu sarežģītības teorijā P problēma ir tāda, kuru var atrisināt polinoma laikā ar vienkāršu algoritmu. Tas joprojām varētu prasīt ievērojamus resursus, taču tas ir gan atrisināms, gan pārbaudāms ar datoru. Šādas problēmas var uzskatīt par ātri atrisināmām, ja vien datoram ir pieejami resursi nepieciešamo aprēķinu veikšanai.
NP problēmas ir sarežģītākas. Nav iespējams izmantot vienu algoritmu, un var būt nepieciešams izmantot papildu opcijas, piemēram, paralēlas Tjūringa mašīnas, kas var izpētīt vairākas iespējas. Problēma varētu būt atrisināma šādā veidā, taču tas prasīs ievērojami vairāk resursu. Šādas problēmas varētu būt vieglākas cilvēkiem, kuri spēj attīstīt loģisko domāšanu, jo lūzuma punkts bieži vien ir loģikas, nevis skaitļošanas grūtības. Ceļojošā pārdevēja problēma, kuras mērķis ir atrast visefektīvāko maršrutu starp vairākām pilsētām maršrutā, ir klasisks NP problēmas piemērs skaitļošanas sarežģītības teorijā.
P un NP problēmu klasificēšana, izmantojot skaitļošanas sarežģītības teoriju, var būt sarežģīts uzdevums, un problēmas var pārvietoties uz priekšu un atpakaļ visā sadalījumā. Neliels skaitļošanas problēmu kopums neietilpst nevienā no kategorijām un dažreiz tiek klasificēts kā neviens, lai to atspoguļotu. Galu galā varētu būt iespējams izstrādāt algoritmu, lai atrisinātu NP problēmu, un dažos gadījumos tas var attiekties uz citām problēmām, kurām ir līdzīga struktūra. Tomēr citos gadījumos tas var būt saistīts ar problēmu. Šādu programmu izpētes process un to risināšanas pieeju izstrāde ir svarīga matemātikas un datorzinātņu joma, kas veicina progresīvu, jaudīgu datorsistēmu izstrādi.