Îninformatica teoretică(d) șimatematică,teoria complexității se concentrează pe clasificareaproblemelor de calcul(d) în funcție de resursele pe care le utilizează și pe analiza relațiilor dintre aceste clase. O problemă de calcul este un task rezolvat de un calculator. O problemă de calcul poate fi rezolvată prin aplicarea mecanică a pașilor matematici, cum ar fi unalgoritm.
O problemă este considerată ca fiind în mod inerent dificilă dacă soluția ei necesită resurse semnificative, indiferent de algoritmul utilizat. Teoria formalizează această idee intuitivă, prin introducerea unormodele matematice de calcul(d) pentru a studia aceste probleme și cuantificândcomplexitatea lor computațională(d), adică cantitatea de resurse necesare pentru a le rezolva, cum ar fi timpul și spațiul de stocare. Sunt utilizate și alte măsuri ale complexității, cum ar fi cantitatea de date comunicate (utilizată încomplexitatea comunicațiilor(d)), numărul deporți dintr-un circuit (utilizat încomplexitatea circuitelor(d)) și numărul de procesoare (utilizate încalculul paralel). Unul dintre rolurile teoriei complexității este de a determina limitele practice a ceea ce pot și nu pot face calculatoarele.Problema P versus NP, una dintre cele șapteprobleme ale Premiului Mileniului(d), este dedicată domeniului complexității computaționale.[1]
În informatica teoretică, acest domeniu este în strânsă legătură cuanaliza algoritmilor(d) șiteoria calculabilității. O distincție cheie între analiza algoritmilor și teoria complexității este că prima este dedicată analizei cantității de resurse necesare unui anumit algoritm pentru a rezolva o problemă, în timp ce cea din urmă pune o întrebare mai generală despre toți algoritmii posibili care ar putea fi utilizați pentru a rezolva aceeași problemă. Mai precis, teoria complexității încearcă să clasifice problemele care pot sau nu pot fi rezolvate cu resurse limitate corespunzător. La rândul său, impunerea de restricții asupra resurselor disponibile este ceea ce distinge teoria complexității de teoria calculabilității: cea din urmă teorie se întreabă ce tipuri de probleme pot fi, în principiu, rezolvate algoritmic.
Oproblemă de calcul(d) poate fi privită ca o colecție infinită deinstanțe împreună cu o mulțime (posibil vidă) desoluții pentru fiecare instanță. Șirul de intrare pentru o problemă de calcul este denumit „instanță a problemei” și nu trebuie confundat cu problema în sine. În teoria complexității, conceptul de problemă se referă la întrebarea abstractă care trebuie rezolvată. În schimb, o instanță a acestei probleme este un enunț destul de concret, care poate servi drept date de intrare pentru o problemă de decizie. De exemplu, fie problematestului de primalitate(d). Instanța este un număr (de exemplu, 15) și soluția este „da” dacă numărul este prim și „nu” în caz contrar (în acest caz, 15 nu este prim și răspunsul este „nu”). Altfel spus,instanța este o anumită intrare a problemei, iarsoluția este ieșirea corespunzătoare intrării date.
Pentru a evidenția și mai mult diferența dintre o problemă și o instanță, fie exemplul versiunii de decizie aproblemei comis-voiajorului: Există o rută de cel mult 2000 de kilometri care trece prin toate cele mai mari 15 orașe ale Germaniei? Răspunsul cantitativ la această problemă particulară este de puțin folos pentru rezolvarea altor cazuri ale problemei, cum ar fi cerința de a găsi un traseu dus-întors prin toate locurile dinMilano a căror lungime totală este de cel mult 10 km. Din acest motiv, teoria complexității se adresează problemelor de calcul și nu cazurilor de probleme specifice.
La abordarea problemelor de calcul, o instanță de problemă este un șir peste unalfabet. De obicei, alfabetul este considerat a fi alfabetul binar (adică mulțimea {0,1}) și astfel șirurile suntșiruri de biți(d). Ca și într-uncomputer din lumea reală, obiectele matematice, altele decât șirurile de biți, trebuie să fie codificate corespunzător. De exemplu,numerele întregi pot fi reprezentate înnotație binară, iargrafurile pot fi codificate direct prinmatricele lor de adiacență sau prin codificarealistelor de adiacență în binar.
Chiar dacă unele demonstrații ale teoremelor de teoria complexității presupun de regulă o alegere concretă a codificării de intrare, discuția trebuie în general să rămână suficient de abstractă pentru a fi independentă de alegerea codificării. Aceasta se poate realiza asigurându-se că diferite reprezentări pot fi transformate eficient una în alta.
Problemele de decizie(d) sunt unul dintre obiectele centrale de studiu în teoria complexității. O problemă de decizie este un tip special de problemă de calcul al cărui răspuns este fieda fienu, sau alternativ fie 1, fie 0. O problemă de decizie poate fi privită ca unlimbaj formal, în care membrii limbajului sunt instanțe a căror ieșire esteda, iar non-membrii sunt acele instanțe a căror ieșire estenu. Obiectivul este de a decide, cu ajutorul unuialgoritm, dacă un șir de intrare dat este membru al limbajului formal luat în considerare. Dacă algoritmul care decide această problemă returnează răspunsulda, se spune că algoritmul acceptă șirul de intrare, în caz contrar se spune că respinge intrarea.
Un exemplu de problemă de decizie este următorul. Datele de intrare sunt ungraf arbitrar. Problema constă în a decide dacă graful dat este sau nuconex. Limbajul formal asociat cu această problemă de decizie este, atunci, mulțimea tuturor grafurilor conexe – pentru a obține o definiție precisă a acestui limbaj, trebuie să se decidă cum sunt codificate grafurile ca șiruri binare.
Oproblemă funcție(d) este o problemă de calcul în care pentru fiecare intrare se așteaptă o singură ieșire (a uneifuncții totale(d)), dar rezultatul este mai complex decât cel al uneiprobleme de decizie(d) – adică rezultatul nu este doar da sau nu. Printre cele mai emblematice exemple se numărăproblema comis-voiajorului șiproblema factorizării întregilor.
Este tentant a crede că noțiunea de probleme funcție este mult mai bogată decât noțiunea de probleme de decizie. Nu este chiar așa, deoarece problemele funcție pot fi transformate în probleme de decizie. De exemplu, înmulțirea a două numere întregi poate fi exprimată ca mulțime de triplete (a, b, c) astfel încât să fie valabilă relațiaa × b = c. A decide dacă o tripletă dată este membră a acestei mulțimi corespunde rezolvării problemei înmulțirii a două numere.
Pentru a măsura dificultatea rezolvării unei probleme de calcul, ar putea fi de dorit să se afle cât timp necesită cel mai bun algoritm pentru a rezolva problema. Timpul de rulare poate depinde însă, în general, de instanță. În special, cazurile mai mari vor necesita mai mult timp pentru rezolvare. Astfel, timpul necesar pentru rezolvarea unei probleme (sau spațiul necesar, sau orice măsură a complexității) este calculat în funcție de dimensiunea instanței. Aceasta este de obicei considerată a fi dimensiunea în biți a datelor de intrare. Teoria complexității este interesată de modul în care algoritmii scalează odată cu creșterea dimensiunii intrării. De exemplu, în problema de a afla dacă un graf este conex, de cât timp este nevoie pentru a rezolva o problemă pentru un graf cu 2n noduri în comparație cu timpul necesar pentru un graf cun noduri?
Dacă dimensiunea intrării esten, timpul necesar poate fi exprimat ca funcție den. Deoarece timpul necesar pentru diferite intrări de aceeași dimensiune poate fi diferit, complexitatea în timp în cel mai rău caz T(n) este definită ca fiind timpul maxim luat pentru toate intrările de dimensiunen. Dacă T(n) este un polinom înn, atunci se spune că este un algoritmîn timp polinomial.Teza lui Cobham(d) susține că o problemă poate fi rezolvată cu o cantitate fezabilă de resurse dacă admite un algoritm în timp polinomial.
O mașină Turing este un model matematic al unei mașini de calcul generale. Este un dispozitiv teoretic care manipulează simbolurile conținute pe o bandă. Mașinile Turing nu sunt concepute ca o tehnologie de calcul practică, ci mai degrabă ca un model teoretic al unei mașini de calcul – un concept care poate corespunde în realitate la fel de bine unui supercalculator avansat sau unui matematician cu creion și hârtie. Se crede că dacă o problemă poate fi rezolvată printr-un algoritm, atunci există o mașină Turing care rezolvă problema. Într-adevăr, acesta este enunțultezei Church-Turing . Mai mult, se știe că tot ceea ce poate fi calculat pe alte modele de calcul cunoscute de noi astăzi, cum ar fi omașină cu acces aleator(d),Jocul Vieții al lui Conway,automate celulare,calcul lambda(d) sau orice limbaj de programare, poate fi calculat pe o mașină Turing. Deoarece mașinile Turing sunt ușor de analizat matematic și se crede că sunt la fel de puternice ca orice alt model de calcul, mașina Turing este cel mai frecvent utilizat model în teoria complexității.
Multe tipuri de mașini Turing sunt folosite pentru a defini clasele de complexitate, cum ar fimașini Turing deterministe,mașini Turing probabilistice(d),mașini Turing nedeterministe,mașini Turing cuantice(d),mașini Turing simetrice(d) șimașini Turing alternante(d). Toate sunt la fel de puternice în principiu, dar atunci când resursele (cum ar fi timpul sau spațiul) sunt limitate, unele dintre acestea pot fi mai puternice decât altele.
O mașină Turing deterministă este cea mai simplă mașină Turing, care folosește o mulțime fixă de reguli pentru a-și determina acțiunile viitoare. O mașină Turing probabilistică este o mașină Turing deterministă cu o sursă suplimentară de biți aleatori. Abilitatea de a lua decizii probabilistice ajută adesea algoritmii să rezolve problemele mai eficient. Algoritmii care folosesc biți aleatori sunt numițialgoritmi randomizați(d). O mașină Turing nedeterministă este o mașină Turing deterministă la care se adaugă nedeterminismul, care permite unei mașini Turing să aibă mai multe acțiuni viitoare posibile dintr-o stare dată. Un fel de a vedea nedeterminismul este că mașina Turing se ramifică în multe căi de calcul posibile la fiecare pas și, dacă rezolvă problema în oricare dintre aceste ramuri, se consideră că a rezolvat problema. Evident, acest model nu este menit să fie un model realizabil fizic, este doar o mașină abstractă interesantă din punct de vedere teoretic, care dă naștere unor clase de complexitate deosebit de interesante.
În literatura de specialitate, au apărut multe propuneri de modele de mașini diferite demașinile Turing standard cu bandă multiplă(d), cum ar fimașinile cu acces aleator(d). Toate aceste modele pot fi convertite unele în celelalte fără a oferi vreun supliment de putere de calcul. Timpul și consumul de memorie al acestor modele alternative poate varia.[2] Ceea ce au în comun toate aceste modele este că mașinile funcționeazădeterminist(d).
Unele probleme de calcul sunt însă mai ușor de analizat în ceea ce privește unele resurse mai neobișnuite. De exemplu, o mașină Turing nedeterministă este un model de calcul căruia i se permite să se ramifice pentru a verifica multe posibilități diferite simultan. Mașina Turing nedeterministă are foarte puțin de-a face cu modul în care dorim fizic să calculăm algoritmi, dar ramificările lor surprind exact multe dintre modelele matematice pe care dorim să le analizăm, astfel încâttimpul nedeterminist(d) este o resursă foarte importantă în analiza problemelor de calcul.
Pentru o definiție precisă a ce înseamnă rezolvarea unei probleme folosind o anumită cantitate de timp și spațiu, se folosește un model de calcul camașina Turing deterministă.Timpul necesar unei mașini Turing deterministeM la intrareax este numărul total de tranziții de stare, sau pași, pe care mașina le efectuează înainte de a se opri și de a da răspunsul („da” sau „nu”). Se spune că o mașină TuringM funcționează în timpf(n) dacă timpul necesar luiM pentru fiecare intrare de lungimen este cel multf(n). O problemă de decizieA poate fi rezolvată în timpf(n) dacă există o mașină Turing care rezolvă problema în timpf(n). Deoarece teoria complexității este interesată de clasificarea problemelor în funcție de dificultatea lor, se definesc mulțimi de probleme pe baza unor criterii. De exemplu, mulțimea problemelor rezolvabile în timpf(n) pe o mașină Turing deterministă este notat cuDTIME(d)(f(n)).
Se pot elabora definiții analoge pentru cerințele de spațiu. Deși timpul și spațiul sunt cele mai cunoscute resurse de complexitate, oricemăsură a complexității(d) poate fi privită ca o resursă de calcul. Măsurile complexității sunt foarte general definite deaxiomele de complexitate Blum(d). Printre alte măsuri ale complexității utilizate în teoria complexității se numărăcomplexitatea comunicării(d),complexitatea circuitelor(d) șicomplexitatea arborelui de decizie(d).
Complexitatea unui algoritm este adesea exprimată folosindnotația Big O.
Complexitatea în cel mai bun, cel mai rău caz și în cazul mediu(d) se referă la trei moduri diferite de a măsura complexitatea în timp (sau orice altă măsură a complexității) pentru diferite intrări de aceeași dimensiune. Deoarece unele intrări de dimensiunean pot fi mai rapid de rezolvat decât altele, definim următoarele complexități:
Ordinea de la ieftin la costisitor este: cel mai bun caz, cazul mediu (cudistribuție uniformă discretă(d)), analiza amortizată, cel mai rău caz.
De exemplu, fie algoritmul de sortare deterministquicksort. Aceasta rezolvă problema sortării unei liste de numere întregi care este dată ca intrare. Cel mai rău caz este atunci când pivotul este întotdeauna cea mai mare sau cea mai mică valoare din listă (deci lista nu este niciodată împărțită). În acest caz, algoritmul dureazăO(n2). Dacă presupunem că toate permutările posibile ale listei de intrare sunt la fel de probabile, timpul mediu necesar pentru sortare esteO(n logn). Cel mai bun caz apare atunci când fiecare pivot împarte lista în jumătate. Acest caz are nevoie tot de timpO(n logn).
Pentru a clasifica timpul de calcul (sau resurse similare, cum ar fi consumul de spațiu), este util să se demonstreze limitele superioare și inferioare ale intervalului maxim de timp cerut de cel mai eficient algoritm care rezolvă o problemă dată. Complexitatea unui algoritm este de obicei considerată a fi complexitatea în cel mai rău caz, dacă nu se specifică altfel. Analiza unui anumit algoritm ține de domeniulanalizei algoritmilor(d). Pentru a demonstra o limită superioarăT(n) a complexității în timp a unei probleme, trebuie să se arate doar că există un anumit algoritm cu timp de rulare cel multT(n). Demonstrarea limitelor inferioare este însă mult mai dificilă, deoarece limitele inferioare fac o afirmație despre toți algoritmii posibili care rezolvă o problemă dată. Expresia „toți algoritmii posibili” include nu doar algoritmii cunoscuți astăzi, ci orice algoritm care ar putea fi descoperit în viitor. Pentru a demonstra o limită inferioară a luiT(n) pentru o problemă este nevoie să se arate că niciun algoritm nu poate avea o complexitate de timp mai mică decâtT(n).
Limitele superioare și inferioare sunt de obicei exprimate folosindnotația Big O, care ascunde factorii constanți și termenii mai mici. Aceasta face ca limitele să fie independente de detaliile specifice ale modelului de calcul utilizat. De exemplu, dacăT(n) = 7n2 + 15n + 40, în notația Big O s-ar scrieT(n) = O(n2).
Oclasă de complexitate este un set de probleme a căror complexitate este strâns legată. Clasele de complexitate mai simple sunt definite de următorii factori:
Unele clase de complexitate au definiții complicate care nu se încadrează în acest cadru. Astfel, o clasă de complexitate tipică are o definiție ca următoarea:
Dar limitarea timpului de calcul de mai sus printr-o funcție concretăf(n) generează adesea clase de complexitate care depind de modelul de mașină ales. De exemplu, limbajul{xx |x este orice șir binar} poate fi rezolvat întimp liniar pe o mașină Turing cu mai multe benzi, dar necesită neapărat timp pătratic în modelul mașinilor Turing cu o singură bandă. Dacă permitem variații polinomiale ale timpului de rulare,teza Cobham-Edmonds(d) afirmă că „complexitățile în timp în oricare două modele rezonabile și generale de calcul sunt legate polinomial” (Goldreich 2008, Chapter 1.2). Aceasta formează baza pentru clasa de complexitateP, care este mulțimea problemelor de decizie rezolvabile de o mașină Turing deterministă în timp polinomial. Mulțimea corespunzătoare de probleme funcție esteFP.
Multe clase de complexitate importante pot fi definite prin delimitarea timpului sau spațiului utilizat de algoritm. Unele clase importante de complexitate ale problemelor de decizie definite în acest mod sunt următoarele:
| Resursă | Determinismul | Clasă de complexitate | Constrângere asupra resursei |
|---|---|---|---|
| Spațiu | Nedeterminist | NSPACE(d)(f(n)) | O(f(n)) |
| NL(d) | O(logn) | ||
| NPSPACE(d) | O(poly(n)) | ||
| NEXPSPACE(d) | O(2poly(n)) | ||
| Determinist | DSPACE(d)(f(n)) | O(f(n)) | |
| L | O(logn) | ||
| PSPACE(d) | O(poly(n)) | ||
| EXPSPACE(d) | O(2poly(n)) | ||
| Timp | Nedeterminist | NTIME(d)(f(n)) | O(f(n)) |
| NP | O(poly(n)) | ||
| NEXPTIME(d) | O(2poly(n)) | ||
| Determinist | DTIME(d)(f(n)) | O(f(n)) | |
| P | O(poly(n)) | ||
| EXPTIME(d) | O(2poly(n)) |
Clasele în spațiu logaritmic nu țin cont neapărat de spațiul necesar pentru a reprezenta problema.
Se pare că PSPACE = NPSPACE și EXPSPACE = NEXPSPACE conformteoremei lui Savitch(d).
Printre alte clase importante de complexitate se numărăBPP(d),ZPP(d) șiRP(d), care sunt definite folosindmașini Turing probabilistice(d);AC(d) șiNC(d), care sunt definite folosind circuite booleene; șiBQP(d) șiQMA(d), care sunt definite folosind mașini Turing cuantice.#P(d) este o clasă importantă de complexitate a problemelor de numărare (nu a problemelor de decizie). Clasele precumIP(d) șiAM(d) sunt definite utilizândsisteme de demonstrație interactive.ALL(d) este clasa tuturor problemelor de decizie.
Pentru clasele de complexitate definite în acest fel, este de dorit să se demonstreze că relaxarea cerințelor privind (de exemplu) timpul de calcul definește într-adevăr o mulțime mai mare de probleme. În special, deși DTIME(n) este conținut în DTIME(n2), ar fi interesant de știut dacă includerea este strictă. Pentru cerințele de timp și spațiu, răspunsul la astfel de întrebări este dat de teoremele de ierarhie în timp și respectiv spațiu. Ele se numescteoreme de ierarhie deoarece induc o ierarhie proprie asupra claselor definite prin constrângerea resurselor respective. Astfel, există perechi de clase de complexitate astfel încât una este inclusă în mod corespunzător în cealaltă. După ce se deduc astfel de incluziuni de mulțimi adecvate, se poate trece la a face afirmații cantitative despre cu cât de mult timp sau spațiu suplimentar este nevoie pentru a crește numărul de probleme care pot fi rezolvate.
Mai precis,teorema de ierarhie în timp(d) afirmă că
Teorema de ierarhie în spațiu(d) afirmă că
Teoremele de ierarhie în timp și spațiu formează baza pentru majoritatea rezultatelor de separare a claselor de complexitate. De exemplu, teorema ierarhiei în timp spune că P este strict conținut în EXPTIME, iar teorema de ierarhie în spațiu spune că L este strict conținut în PSPACE.
Multe clase de complexitate sunt definite folosind conceptul de reducere. O reducere este o transformare a unei probleme într-o altă problemă. Ea surprinde noțiunea informală că o problemă este cel mult la fel de dificilă ca o altă problemă. De exemplu, dacă o problemăX poate fi rezolvată folosind un algoritm pentruY, atunciX nu este mai dificil decâtY, și se spune căXse reduce laY. Există multe tipuri diferite de reduceri, bazate pe metoda reduceriu, cum ar fi reducerile Cook, reducerile Karp și reducerile Levin, și limita de complexitate a reducerilor, cum ar fireducerile în timp polinomial(d) saureducerile în spațiu logaritmic(d).
Reducerea cel mai frecvent utilizată este o reducere în timp polinomial. Aceasta înseamnă că procesul de reducere durează un timp polinomial. De exemplu, problema ridicării la pătrat a unui număr întreg poate fi redusă la problema înmulțirii a două numere întregi. Aceasta înseamnă că un algoritm pentru înmulțirea a două numere întregi poate fi folosit și pentru a ridica la pătrat un număr întreg. Într-adevăr, aceasta se poate face dând aceeași valoare la ambele intrări ale algoritmului de multiplicare. Astfel, vedem că ridicarea la pătrat nu este mai dificilă decât înmulțirea, deoarece ridicarea la pătrat poate fi redusă la înmulțire.
Aceasta motivează conceptul de problemă tare pentru o clasă de complexitate. O problemăX estetare pentru o clasă de problemeC dacă orice problemă dinC poate fi redusă laX. Astfel, nicio problemă dinC nu este mai grea decâtX, deoarece un algoritm pentruX ne permite să rezolvăm orice problemă dinC. Noțiunea de probleme tari depinde de tipul de reducere utilizat. Pentru clasele de complexitate mai mari decât P, sunt utilizate în mod obișnuit reducerile de timp polinomial. În special, mulțimea problemelor care sunt tari pentru NP constituie mulțimea problemelorNP-hard.
Dacă o problemăX este înC și este tare pentruC, atunci se spune căX estecompletă(d) pentruC. Aceasta înseamnă căX este cea mai tare problemă dinC. (Deoarece multe probleme ar putea fi la fel de tari, s-ar putea spune căX este una dintre cele mai tari probleme dinC.) Astfel, clasa de problemeNP-complete conține cele mai tari probleme din NP, în sensul că acestea sunt cel mai probabil să nu fie în P. Pentru că problema P = NP nu este rezolvată, posibilitatea de a reduce o problemă NP-completă cunoscută, Π2, la o altă problemă, Π1, ar demonstra că nu există o soluție cunoscută în timp polinomial pentru Π1. Aceasta se datorează faptului că o soluție în timp polinomial pentru Π1 ar da o soluție în timp polinomial pentru Π2. Similar, deoarece toate problemele NP pot fi reduse la această mulțime, găsirea unei problemeNP-complete care poate fi rezolvată în timp polinomial ar însemna că P = NP.[3]
Clasa de complexitate P este adesea considerată a fi o abstractizare matematică care modelează acele sarcini de calcul care admit un algoritm eficient. Această ipoteză se numeșteteza Cobham-Edmonds(d). Pe de altă parte, clasa de complexitateNP conține multe probleme pe care oamenii ar dori să le rezolve eficient, dar pentru care nu se cunoaște un algoritm eficient, cum ar fiproblema satisfiabilității booleene(d),problema drumului hamiltonian șiproblema acoperirii vârfurilor(d). Deoarece mașinile Turing deterministe sunt un caz special de mașini Turing nedeterministe, se observă cu ușurință că orice problemă din P este de asemenea membră a clasei NP.
Întrebarea dacă P este egal cu NP este una dintre cele mai importante întrebări deschise din informatica teoretică din cauza amplelor implicații pe care le-ar avea o soluție.[3] Dacă răspunsul este da, se poate demonstra că multe probleme importante au soluții mai eficiente. Printre acestea se numără diferite tipuri de probleme deprogramare cu numere întregi(d) dincercetarea operațională(d), multe probleme înlogistică,predicția structurii proteinelor(d) înbiologie[5] și capacitatea de a găsi dovezi formale ale teoremelor dematematică pură.[6] Problema P versus NP este una dintreProblemele Premiului Mileniului(d) propuse deInstitutul de Matematică Clay(d). Există un premiu de 1.000.000 de dolari pentru rezolvarea problemei.[7]
Ladner a arătat că dacăP ≠NP, atunci există probleme înNP care nu sunt niciP, niciNP-complete.[4] Astfel de probleme se numesc problemeNP-intermediare(d).Problema izomorfismului de grafuri(d),problema logaritmului discret șiproblema factorizării întregilor sunt exemple de probleme considerate a fi NP-intermediare. Ele sunt unele dintre puținele probleme NP despre care nu se știe dacă suntP sauNP-complete.
Problema izomorfismului de grafuri(d) este problema de calcul care cere să se determine dacă douăgrafuri finite suntizomorfe. O problemă importantă nerezolvată în teoria complexității este dacă problema izomorfismului de grafuri esteP,NP-completă sau NP-intermediară. Răspunsul nu este cunoscut, dar se crede că problema cel puțin nu este NP-completă.[8] Dacă izomorfismul de grafuri este NP-complet,ierarhia timpilor polinomiali(d) se pliază la al doilea nivel.[9] Deoarece se crede că ierarhia polinomială nu se pliază la niciun nivel finit, se crede și că izomorfismul de grafuri nu este NP-complet. Cel mai bun algoritm pentru această problemă, datorat luiLászló Babai(d) șiEugene Luks(d), are timpul de rulare pentru grafuri cun noduri, deși unele lucrări recente ale lui Babai oferă câteva noi perspective cu potențial în acest sens.
Problema factorizării întregilor este problema de calcul de determinare adescompunerii în factori primi a unui număr întreg dat. Exprimată ca o problemă de decizie, este problema de a decide dacă numărul primit la intrare are un factor prim mai mic decâtk. Nu se cunoaște un algoritm eficient de factorizare a întregilor, iar acest fapt formează baza mai multor sisteme criptografice moderne, cum ar fi algoritmulRSA. Problema factorizării întregilor esteNP șico-NP (și chiar în UP și co-UP[10]). Dacă problema esteNP-completă, atunci ierarhia timpilor polinomiali se va plia la primul său nivel (adică,NP va fi egal cuco-NP). Cel mai cunoscut algoritm pentru factorizarea întregilor esteciurul pe corpuri de numere generalizat(d), care necesită un timp de[11] pentru factorizarea unui număr întreg imparn. Cu toate acestea, cel mai cunoscutalgoritm cuantic(d) pentru această problemă,algoritmul lui Shor(d), rulează în timp polinomial. Aceasta nu spune însă prea multe despre unde se află problema în ceea ce privește clasele de complexitate non-cuantică.
Multe clase de complexitate cunoscute sunt suspectate a fi inegale, dar acest lucru nu a fost demonstrat încă. De exempluP ⊆NP ⊆PP(d) ⊆PSPACE, dar este posibil caP =PSPACE. DacăP nu este egal cuNP, atunciP nu este egal nici cuPSPACE. Deoarece există multe clase de complexitate cunoscute întreP șiPSPACE, cum ar fiRP,BPP,PP,BQP,MA,PH etc., este posibil ca toate aceste clase de complexitate să se plieze într-o singură clasă. Demonstrarea că oricare dintre aceste clase sunt inegale ar fi o descoperire majoră în teoria complexității.
Pe aceeași linie,Co-NP(d) este clasa care conține problemelecomplementare(d) (adică probleme cu răspunsurileda /nu inversate) ale problemelorNP. Se crede[12] căNP nu este egal cuco-NP, dar încă nu s-a demonstrat. Este clar că dacă aceste două clase de complexitate nu sunt egale atunciP nu este egal cuNP, deoareceP =co-P. Astfel dacăP =NP am aveaco-P =co-NP de undeNP =P =co-P =co-NP.
Analog, nu se știe dacăL (mulțimea tuturor problemelor care pot fi rezolvate în spațiu logaritmic) este strict conținută înP sau egală cuP. Din nou, există multe clase de complexitate între cele două, cum ar fiNL șiNC și nu se știe dacă sunt clase distincte sau egale.
Se bănuiește căP șiBPP sunt egale. Cu toate acestea, râmâne în prezent deschisă problema dacăBPP =NEXP.
O problemă care poate fi rezolvată în teorie (de exemplu, având în vedere resurse mari, dar finite, în special timp), dar pentru care în practicăorice soluție necesită prea multe resurse pentru a fi utilă, se numeșteproblemă netractabilă.[13] În schimb, o problemă care poate fi rezolvată în practică se numeșteproblemă tractabilă, literalmente „o problemă care poate fi rezolvată”. Termenulnefezabil (literalmente „care nu se poate face”) este uneori folosit interschimbabil cunetractabil,[14] deși acest lucru riscă confuzia cusoluțiile fezabile(d) dinoptimizarea matematică.[15]
Problemele tractabile sunt frecvent identificate cu probleme care au soluții în timp polinomial (P,PTIME); aceasta esteteza Cobham-Edmonds(d). Problemele despre care se știe că sunt netractabile în acest sens le includ și pe cele care sunt dureEXPTIME(d). Dacă NP nu este același cu P, atunci problemeleNP-hard sunt și ele netractabile în acest sens.
Identificarea aceasta este însă imprecisă: o soluție în timp polinomial cu grad mare sau cu un coeficient mare la primul termen crește rapid și poate fi nepractică pentru probleme de dimensiune curentă; dimpotrivă, o soluție în timp exponențial care crește însă lent poate fi practică pe o intrare realistă, sau o soluție care durează mult timp pe cazul cel mai rău poate dura puțin timp în majoritatea cazurilor sau în cazul mediu și, prin urmare, poate fi încă practică. A spune că o problemă nu este în P nu înseamnă că toate cazurile principale ale problemei sunt dificile și nici măcar că majoritatea lor sunt dificile. De exemplu, s-a demonstrat că problema deciziei dinaritmetica Presburger nu este în P, totuși s-au scris algoritmi care rezolvă problema în timp rezonabil în majoritatea cazurilor. În mod similar, algoritmii pot rezolvaproblema rucsacului (care este NP-completă) pe o gamă largă de dimensiuni în timp mai rapid decât cel pătratic, iarrezolvitoarele SAT(d) gestionează în mod obișnuit cazuri mari aleproblemei satisfiabilității booleene(d), care și ea este NP-completă.
Pentru a vedea de ce algoritmii în timp exponențial sunt în general inutilizabili în practică, se poate lua de exemplu în considerare un program care face 2n operațiuni înainte de a se opri. Pentru unn mic, cum ar fi 100, și presupunând, de dragul exemplului, că calculatorul efectuează 1012 operații în fiecare secundă, programul ar rula timp de aproximativ 4 × 1010 ani, același ordin de mărime cavârsta universului. Chiar și cu un calculator mult mai rapid, programul ar fi util doar pentru cazuri foarte mici și, în acest sens, netractabilitatea unei probleme este oarecum independentă de progresul tehnologic. Cu toate acestea, un algoritm în timp exponențial care necesită 1,0001n operații este practic până cândn devine relativ mare.
În mod similar, un algoritm în timp polinomial nu este întotdeauna practic. Dacă timpul său de funcționare este, să zicem,n15, este nerezonabil să îl considerăm eficient și este încă inutil, cu excepția cazurilor mici. Într-adevăr, în practică, chiar și algoritmii ce rulează în timp de ordinuln3 saun2 sunt adesea nepractici pentru dimensiuni realiste ale problemelor.
Teoria complexității continue se poate referi la teoria complexității problemelor care implică funcții continue care sunt aproximate prin discretizări, care sunt studiate deanaliza numerică. O abordare a teoriei complexității analizei numerice[16] estecomplexitatea bazată pe informații(d).
Teoria complexității continue se poate referi și la teoria complexității utilizăriicalculului analogic, care utilizeazăsisteme dinamice continue șiecuații diferențiale.Teoria controlului(d) poate fi considerată o formă de calcul și ecuațiile diferențiale sunt utilizate în modelarea sistemelor de timp continuu și a celor hibride în timp continuu și discret.[17]
Unul din primele exemple de analiză a complexității algoritmilor este analiza timpului de rulare aalgoritmului lui Euclid realizată deGabriel Lamé în 1844.
Înainte de a începe cercetarea actuală dedicată în mod explicit complexității problemelor algoritmice, diferite baze au fost puse de diferiți cercetători. Cea mai influentă dintre acestea a fost definiția mașinilor Turing de cătreAlan Turing în 1936, ceea ce s-a dovedit a fi un model simplificat foarte robustt și flexibil al unui calculator.
Începutul studiilor sistematice în domeniul complexității computaționale este considerat a fi lucrarea din 1965 „On the Computational Complexity of Algorithms” (lit. „Despre complexitatea computațională a algoritmilor”) deJuris Hartmanis șiRichard E. Stearns, care a stabilit definițiilecomplexității în timp șicomplexității în spațiu(d) și a demonstrat teoremele ierarhiei. În plus, în 1965,Edmonds a sugerat că un algoritm poate fi considerat „bun” dacă are timpul de rulare limitat de o funcție polinomială de mărimea intrării.[18]
Printre primele lucrări care au studiat problemele rezolvabile de mașinile Turing cu resurse limitate specifice se numără definiția dată deJohn Myhill(d)automatelor liniare mărginite(d) (Myhill 1960), studiul mulțimilor rudimentare al luiRaymond Smullyan (1961), precum și lucrarea luiHisao Yamada(d)[19] despre calculul în timp real (1962). Ceva mai devreme,Boris Trakhtenbrot (1956), un pionier al domeniului din URSS, a studiat o altă măsură specifică a complexității.[20] El își amintește:
„Interesul [meu] inițial [în teoria automatelor] era însă din ce în ce mai mult dat la o parte în favoarea complexității computaționale, o interesantă fuziune de metode combinatorice, moștenite dinteoria comutației(d), cu arsenalul conceptual al teoriei algoritmilor. Aceste idei îmi trecuseră prin minte mai devreme, în 1955, când am avansat termenul «funcție semnalizatoare» [pentru un concept] astăzi cunoscut drept «măsură a complexității».[21]”
În 1967, Manuel Blum a formulat un set de axiome (numite astăziaxiomele lui Blum(d)) care specificau proprietățile dorite ale măsurilor complexității pe mulțimea funcțiilor calculabile și a demonstrat un rezultat important, așa numitateoremă a accelerării(d). Domeniul a început să înflorească în 1971 cândStephen Cook șiLeonid Levin(d)au demonstrat(d) existența problemelor cu relevanță practică care suntNP-complete. În 1972, Richard Karp a dus ideea cu un mare pas înainte cu lucrarea sa „Reductibilitatea între problemele combinatorice”, în care a arătat că 21 de probleme decombinatorică șiteoria grafurilor, fiecare cunoscută pentru netractabilitatea lor computațională, sunt NP-complete.
,doi:10.1089/cmb.1998.5.27,PMID 9541869. . ,ISSN 0001-0782 ,Bibcode:2002CSE.....4c..31M,doi:10.1109/5992.998639,ISSN 1521-9615 
