Teorija računalne složenosti je područje matematike i računalnih znanosti koje se bavi resursima potrebnim za rješavanje problema na računalnim sustavima. Dostupne su brojne tehnike za određivanje zahtjeva za resursima problema. Neki problemi možda neće biti izvedivi na postojećim računalnim sustavima zbog njihovih zahtjeva za resursima. Istraživači klasificiraju probleme prema težini i mogu podijeliti izračune na polinomske (P) naspram neterminističke polinomske (NP) probleme.
Rješavanje računanja zahtijeva resurse kao što su vrijeme, prostor za pohranu i hardver. Računalni sustav može imati ograničenja koja problem čine funkcionalno nemogućim za rješavanje jer nema raspoloživih resursa. Kako se računalna tehnologija poboljšava, ranije nerješivi problem mogao bi postati rješiv uz pomoć nove tehnologije i istraživanja u području teorije računalne složenosti. Rješivost problema nije nužno određena njegovom složenošću već algoritmima koji se koriste za njegovo rješavanje.
U teoriji računske složenosti, P problem je onaj koji se može riješiti u polinomskom vremenu s jednostavnim algoritmom. To bi još uvijek moglo zahtijevati znatne resurse, ali je i rješivo i provjerljivo računalom. Takvi se problemi mogu smatrati brzo rješivim sve dok računalo ima raspoložive resurse za rukovanje potrebnim izračunima.
NP problemi su složeniji. Nije moguće primijeniti jedan algoritam, a možda će biti potrebno koristiti naprednije opcije, kao što su paralelni Turingovi strojevi koji mogu istraživati nekoliko opcija. Problem bi se mogao riješiti na ovaj način, ali će zahtijevati znatno više sredstava. Takvi bi problemi mogli biti lakši za ljudske operatere koji su sposobni za napredno logičko razmišljanje, jer je prijelomna točka često logička, a ne puka poteškoća u računanju. Problem trgovačkog putnika, u kojem je cilj pronaći najučinkovitiju rutu između više gradova duž rute, klasičan je primjer NP problema u teoriji računske složenosti.
Klasifikacija P naspram NP problema kroz računsku teoriju složenosti može biti složen zadatak, a problemi se mogu pomicati naprijed-natrag preko podjele. Mali skup računskih problema ne uklapa se uredno ni u jednu kategoriju i ponekad se ne klasificiraju kao ni jedan da bi to odražavali. Na kraju bi moglo biti moguće razviti algoritam za rješavanje NP problema, au nekim slučajevima, mogao bi se primijeniti na druge probleme koji imaju sličnu strukturu. U drugima, međutim, može biti specifičan problem. Proces istraživanja takvih programa i razvoj pristupa njihovom rješavanju važno je područje matematike i računarstva koje pridonosi razvoju naprednih, moćnih računalnih sustava.