Teorija računske kompleksnosti je področje matematike in računalništva, ki se ukvarja z viri, potrebnimi za reševanje problemov v računalniškem sistemu. Za določitev potreb po virih za težavo so na voljo številne tehnike. Nekatere težave morda ne bodo izvedljive v obstoječih računalniških sistemih zaradi njihovih zahtev po virih. Raziskovalci razvrščajo probleme po težavnosti in lahko razdelijo izračune na polinomske (P) proti neterministične polinomske (NP) probleme.
Reševanje računanja zahteva vire, kot so čas, prostor za shranjevanje in strojna oprema. Računalniški sistem ima lahko omejitve, zaradi katerih je problem funkcionalno nemogoče rešiti, ker nima razpoložljivih virov. Ko se računalniška tehnologija izboljšuje, lahko prej nerešljiv problem postane rešljiv s pomočjo nove tehnologije in raziskav na področju teorije računske kompleksnosti. Rešljivost problema ni nujno določena z njegovo kompleksnostjo, temveč z algoritmi, ki se uporabljajo za njegovo reševanje.
V teoriji računske kompleksnosti je problem P tisti, ki ga je mogoče rešiti v polinomskem času z enostavnim algoritmom. Morda še vedno zahteva znatna sredstva, vendar ga je mogoče rešiti in preveriti z računalnikom. Takšne težave bi si lahko predstavljali kot hitro rešljive, dokler ima računalnik razpoložljive vire za izvajanje potrebnih izračunov.
Problemi NP so bolj zapleteni. Ni mogoče uporabiti enega samega algoritma in morda bo treba uporabiti naprednejše možnosti, kot so vzporedni Turingovi stroji, ki lahko raziskujejo več možnosti. Težavo bi bilo mogoče rešiti na ta način, vendar bo zahtevalo bistveno več sredstev. Takšni problemi so lahko lažji za človeške operaterje, ki so sposobni naprednega logičnega razmišljanja, saj je prelomna točka pogosto logična in ne zgolj računska težava. Problem potujočega prodajalca, pri katerem je cilj najti najučinkovitejšo pot med številnimi mesti vzdolž poti, je klasičen primer problema NP v teoriji računske kompleksnosti.
Razvrstitev problemov P proti NP s pomočjo teorije kompleksnosti računanja je lahko zapletena naloga in težave se lahko premikajo naprej in nazaj čez razkorak. Majhen nabor računskih problemov se ne ujema čisto v nobeno od kategorij in včasih ni razvrščen kot nobena, da bi to odražali. Sčasoma bi bilo mogoče razviti algoritem za rešitev problema NP, v nekaterih primerih pa se lahko uporablja za druge probleme, ki imajo podobno strukturo. Pri drugih pa je lahko problem specifičen. Proces raziskovanja tovrstnih programov in razvoja pristopov za njihovo reševanje je pomembno področje matematike in računalništva, ki prispeva k razvoju naprednih, zmogljivih računalniških sistemov.