Teoria complexității computaționale este o zonă a matematicii și informaticii care se preocupă de resursele necesare pentru a rezolva probleme pe un sistem informatic. Sunt disponibile un număr de tehnici pentru a determina cerințele de resurse ale unei probleme. Este posibil ca unele probleme să nu fie fezabile pe sistemele informatice existente din cauza necesităților lor de resurse. Cercetătorii clasifică problemele după dificultate și pot împărți calculele în probleme polinomiale (P) versus probleme polinomiale neterministe (NP).
Rezolvarea unui calcul necesită resurse precum timp, spațiu de stocare și hardware. Un sistem informatic poate avea limitări care fac o problemă imposibil de rezolvat din punct de vedere funcțional, deoarece nu are resursele disponibile. Pe măsură ce tehnologia computerelor se îmbunătățește, o problemă nerezolvată anterior ar putea deveni rezolvabilă cu ajutorul noilor tehnologii și cercetări în domeniul teoriei complexității computaționale. Rezolvabilitatea unei probleme nu este determinată neapărat de complexitatea acesteia, ci de algoritmii folosiți pentru a o rezolva.
În teoria complexității computaționale, o problemă P este una care poate fi rezolvată în timp polinomial cu un algoritm simplu. Ar putea încă necesita resurse substanțiale, dar este atât rezolvabil, cât și verificabil de computer. Astfel de probleme ar putea fi considerate la fel de rezolvabile atâta timp cât un computer are resursele disponibile pentru a gestiona calculele necesare.
Problemele NP sunt mai complexe. Nu este posibil să se aplice un singur algoritm și ar putea fi necesar să se utilizeze opțiuni mai avansate, cum ar fi mașinile Turing paralele care pot explora mai multe opțiuni. Problema poate fi rezolvată în acest fel, dar va necesita mult mai multe resurse. Asemenea probleme ar putea fi mai ușoare pentru operatorii umani care sunt capabili de gândire logică avansată, deoarece punctul de răsturnare este adesea unul de logică, mai degrabă decât de dificultatea de calcul. Problema vânzătorului ambulant, în care scopul este de a găsi cea mai eficientă rută între un număr de orașe de-a lungul unei rute, este un exemplu clasic de problemă NP în teoria complexității computaționale.
Clasificarea problemelor P versus NP prin teoria complexității computaționale poate fi o sarcină complexă, iar problemele se pot deplasa înainte și înapoi de-a lungul diviziunii. Un mic set de probleme de calcul nu se încadrează perfect în nici una dintre categorii și uneori nu sunt clasificate ca nici una pentru a reflecta acest lucru. În cele din urmă, ar putea fi posibilă dezvoltarea unui algoritm pentru a rezolva o problemă NP și, în unele cazuri, s-ar putea aplica altor probleme care au o structură similară. În altele, totuși, poate fi specifică problemei. Procesul de explorare a unor astfel de programe și de dezvoltare a abordărilor pentru a le rezolva este un domeniu important al matematicii și informaticii care contribuie la dezvoltarea sistemelor informatice avansate, de mare putere.