Vizualizare sursă pentru „Teoria complexității”


În {{Ill-wd|Q2878974|3=informatica teoretică}} și [[matematică]], '''teoria complexității''' se concentrează pe clasificarea {{Ill-wd|Q3435924|3=problemelor de calcul}} î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 un [[algoritm]].

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 unor {{Ill-wd|Q2651576|3=modele matematice de calcul}} pentru a studia aceste probleme și cuantificând {{Ill-wd|Q5157286|3=complexitatea lor computațională}}, 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ă în {{Ill-wd|Q5154130|3=complexitatea comunicațiilor}}), numărul de [[Poartă logică|porți]] dintr-un circuit (utilizat în {{Ill-wd|Q1055112|3=complexitatea circuitelor}}) și numărul de procesoare (utilizate în [[Calcul paralel|calculul paralel]]). Unul dintre rolurile teoriei complexității este de a determina limitele practice a ceea ce pot și nu pot face calculatoarele. [[Clasele de complexitate P și NP|Problema P versus NP]], una dintre cele șapte {{Ill-wd|Q727000|3=probleme ale Premiului Mileniului}}, este dedicată domeniului complexității computaționale.<ref>{{Citat web|url=http://www.claymath.org/millennium-problems/p-vs-np-problem|titlu=P vs NP Problem {{!}} Clay Mathematics Institute|lucrare=www.claymath.org|limbă=en|accessdate=2023-06-28|archive-date=2018-07-06|archive-url=https://web.archive.org/web/20180706075006/http://www.claymath.org/millennium-problems/p-vs-np-problem|dead-url=yes}}</ref>

În informatica teoretică, acest domeniu este în strânsă legătură cu {{Ill-wd|Q333464|3=analiza algoritmilor}} și [[teoria 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.

== Probleme de calcul ==
[[Image:TSP Deutschland 3.png|thumb|upright=1.5|Turul unui comis-voiajor prin 14 orașe germane.]]
=== Instanțe de probleme ===
O {{Ill-wd|Q3435924|3=problemă de calcul}} poate fi privită ca o colecție infinită de ''instanțe'' împreună cu o mulțime (posibil vidă) de ''soluț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 problema {{Ill-wd|Q829546|3=testului de primalitate}}. 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, iar ''soluț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 a [[Problema comis-voiajorului|problemei 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 din [[Milano]] a căror lungime totală este de cel mult 10&nbsp;km. Din acest motiv, teoria complexității se adresează problemelor de calcul și nu cazurilor de probleme specifice.

=== Reprezentarea cazurilor problematice ===
La abordarea problemelor de calcul, o instanță de problemă este un șir peste un [[Alfabet (informatică)|alfabet]]. De obicei, alfabetul este considerat a fi alfabetul binar (adică mulțimea {0,1}) și astfel șirurile sunt {{Ill-wd|Q1992074|3=șiruri de biți}}. Ca și într-un [[Calculator|computer]] din lumea reală, obiectele matematice, altele decât șirurile de biți, trebuie să fie codificate corespunzător. De exemplu, [[Număr întreg|numerele întregi]] pot fi reprezentate în [[Sistem binar|notație binară]], iar [[Graf|grafurile]] pot fi codificate direct prin [[Matrice de adiacență|matricele lor de adiacență]] sau prin codificarea [[Listă de adiacență|listelor 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 ca limbaje formale ===
[[Image:Decision Problem.svg|thumb|upright|O {{Ill-wd|Q3262192|3=problemă de decizie}} are doar două ieșiri posibile, ''da'' sau ''nu'' (sau 1 sau 0) oricare ar fi intrarea.]]
{{Ill-wd|Q3262192|3=Problemele de decizie}} 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 fie ''da'' fie ''nu'', sau alternativ fie 1, fie 0. O problemă de decizie poate fi privită ca un [[limbaj formal]], în care membrii limbajului sunt instanțe a căror ieșire este ''da'', iar non-membrii sunt acele instanțe a căror ieșire este ''nu''. Obiectivul este de a decide, cu ajutorul unui [[algoritm]], dacă un șir de intrare dat este membru al limbajului formal luat în considerare. Dacă algoritmul care decide această problemă returnează răspunsul ''da'', 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 un [[graf]] arbitrar. Problema constă în a decide dacă graful dat este sau nu [[Conexitate (teoria grafurilor)|conex]]. Limbajul formal asociat cu această problemă de decizie este, atunci, mulțimea tuturor grafurilor conexe{{Mdash}} pentru a obține o definiție precisă a acestui limbaj, trebuie să se decidă cum sunt codificate grafurile ca șiruri binare.

=== Probleme funcție ===
O {{Ill-wd|Q906766|3=problemă funcție}} este o problemă de calcul în care pentru fiecare intrare se așteaptă o singură ieșire (a unei {{Ill-wd|Q1756942|3=funcții totale}}), dar rezultatul este mai complex decât cel al unei {{Ill-wd|Q3262192|3=probleme de decizie}}{{Mdash}} adică rezultatul nu este doar da sau nu. Printre cele mai emblematice exemple se numără [[problema comis-voiajorului]] și [[Descompunerea în factori primi|problema 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'',&nbsp;''b'',&nbsp;''c'') astfel încât să fie valabilă relația ''a''&nbsp;×&nbsp;''b''&nbsp;=&nbsp;''c''. A decide dacă o tripletă dată este membră a acestei mulțimi corespunde rezolvării problemei înmulțirii a două numere.

=== Măsurarea dimensiunii unei instanțe ===
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 2''n'' noduri în comparație cu timpul necesar pentru un graf cu ''n'' noduri?

Dacă dimensiunea intrării este ''n'', timpul necesar poate fi exprimat ca funcție de ''n''. 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 dimensiune ''n''. Dacă T(''n'') este un polinom în ''n'', atunci se spune că este un algoritm [[Complexitate în timp|în timp polinomial]]. {{Ill-wd|Q5138877|3=Teza lui Cobham}} susține că o problemă poate fi rezolvată cu o cantitate fezabilă de resurse dacă admite un algoritm în timp polinomial.

== Modele de mașină și măsuri ale complexității ==

=== Mașina Turing ===
[[File:Turing machine 2b.svg|thumb|right|Ilustrarea unei mașini Turing]]
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{{Mdash}} 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țul [[Teza Church-Turing|tezei 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 o {{Ill-wd|Q2565212|3=mașină cu acces aleator}}, [[Jocul Vieții al lui Conway]], [[Automat celular|automate celulare]], {{Ill-wd|Q242028|3=calcul lambda}} 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 fi [[Mașină Turing|mașini Turing deterministe]], {{Ill-wd|Q1191836|3=mașini Turing probabilistice}}, [[Mașină Turing nedeterministă|mașini Turing nedeterministe]], {{Ill-wd|Q765620|3=mașini Turing cuantice}}, {{Ill-wd|Q7661303|3=mașini Turing simetrice}} și {{Ill-wd|Q438833|3=mașini Turing alternante}}. 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ți {{Ill-wd|Q583461|3=algoritmi randomizați}}. 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.

=== Alte modele de mașini ===
În literatura de specialitate, au apărut multe propuneri de modele de mașini diferite de {{Ill-wd|Q7854962|3=mașinile Turing standard cu bandă multiplă}}, cum ar fi {{Ill-wd|Q2565212|3=mașinile cu acces aleator}}. 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.<ref>See {{Harvnb|Arora|Barak|2009|loc=Chapter 1: The computational model and why it doesn't matter}}</ref> Ceea ce au în comun toate aceste modele este că mașinile funcționează {{Ill-wd|Q1064349|3=determinist}}.

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ât {{Ill-wd|Q1933581|3=timpul nedeterminist}} este o resursă foarte importantă în analiza problemelor de calcul.

=== Măsura complexității ===
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 ca [[Mașină Turing|mașina Turing deterministă]]. ''Timpul necesar'' unei mașini Turing deterministe ''M'' la intrarea ''x'' 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ă Turing ''M'' funcționează în timp {{Math|''f''(''n'')}} dacă timpul necesar lui ''M'' pentru fiecare intrare de lungime {{Math|''n''}} este cel mult {{Math|''f''(''n'')}}. O problemă de decizie ''A'' poate fi rezolvată în timp {{Math|''f''(''n'')}} dacă există o mașină Turing care rezolvă problema în timp {{Math|''f''(''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 timp {{Math|''f''(''n'')}} pe o mașină Turing deterministă este notat cu {{Ill-wd|Q1155831|3=DTIME}}({{Math|''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, orice {{Ill-wd|Q723897|3=măsură a complexității}} poate fi privită ca o resursă de calcul. Măsurile complexității sunt foarte general definite de {{Ill-wd|Q4059945|3=axiomele de complexitate Blum}}. Printre alte măsuri ale complexității utilizate în teoria complexității se numără {{Ill-wd|Q1055112|3=complexitatea comunicării}}, {{Ill-wd|Q1055112|3=complexitatea circuitelor}} și {{Ill-wd|Q5249246|3=complexitatea arborelui de decizie}}.

Complexitatea unui algoritm este adesea exprimată folosind [[notația Big O]].

=== Complexitatea în cazul cel mai bun, cel mai rău și mediu ===
[[File:Sorting quicksort anim.gif|thumb|Vizualizare a [[algoritm]]ului [[quicksort]] care are {{Ill-wd|Q186094|3=performanța în cazul mediu}} <math>\mathcal{O}(n\log n)</math>.]]
{{Ill-wd|Q186094|3=Complexitatea în cel mai bun, cel mai rău caz și în cazul mediu}} 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 dimensiunea ''n'' pot fi mai rapid de rezolvat decât altele, definim următoarele complexități:

# Complexitatea în cel mai bun caz: Aceasta este complexitatea rezolvării problemei pentru cea mai bună intrare de dimensiune ''n''.
# Complexitatea medie a cazului: Aceasta este complexitatea rezolvării problemei în medie. Această complexitate este definită doar în raport cu o [[Distribuții de probabilitate|distribuție de probabilitate]] între intrări. De exemplu, dacă se presupune că toate intrările de aceeași dimensiune sunt la fel de probabil să apară, complexitatea medie a cazului poate fi definită în raport cu distribuția uniformă pe toate intrările de dimensiune ''n''.
# {{Ill-wd|Q331716|3=Analiza amortizată}} ia în considerare atât operațiunile costisitoare, cât și cele mai puțin costisitoare împreună pe întreaga serie de operații ale algoritmului.
# Complexitatea în cel mai rău caz: Aceasta este complexitatea rezolvării problemei pentru cea mai proastă intrare de dimensiune ''n''.

Ordinea de la ieftin la costisitor este: cel mai bun caz, cazul mediu (cu {{Ill-wd|Q3574718|3=distribuție uniformă discretă}}), analiza amortizată, cel mai rău caz.

De exemplu, fie algoritmul de sortare determinist [[quicksort]]. 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ă [[Notația Big O|O]]({{Math|''n''<sup>2</sup>}}). Dacă presupunem că toate permutările posibile ale listei de intrare sunt la fel de probabile, timpul mediu necesar pentru sortare este {{Math|''O''(''n'' log ''n'')}}. Cel mai bun caz apare atunci când fiecare pivot împarte lista în jumătate. Acest caz are nevoie tot de timp {{Math|''O''(''n'' log ''n'')}}.

=== Limitele superioare și inferioare ale complexității problemelor ===
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 domeniul {{Ill-wd|Q333464|3=analizei algoritmilor}}. 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 mult ''T''(''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 lui ''T''(''n'') pentru o problemă este nevoie să se arate că niciun algoritm nu poate avea o complexitate de timp mai mică decât ''T''(''n'').

Limitele superioare și inferioare sunt de obicei exprimate folosind [[notaț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'')&nbsp;=&nbsp;7''n''<sup>2</sup>&nbsp;+&nbsp;15''n''&nbsp;+&nbsp;40, în notația Big O s-ar scrie ''T''(''n'')&nbsp;=&nbsp;O(''n<sup>2</sup>)''.

== Clasele de complexitate ==

=== Definirea claselor de complexitate ===
O '''clasă 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:

* Tipul problemei de calcul: cele mai frecvent utilizate probleme sunt problemele de decizie. Clasele de complexitate pot fi însă definite pe baza {{Ill-wd|Q906766|3=problemelor funcție}}, {{Ill-wd|Q5177154|3=problemelor de numărare}}, {{Ill-wd|Q984063|3=problemelor de optimizare}}, {{Ill-wd|Q130203|3=problemelor de promisiuni}} etc.
* Modelul de calcul: Cel mai comun model de calcul este mașina Turing deterministă, dar multe clase de complexitate se bazează pe mașini Turing nedeterministe, {{Ill-wd|Q837479|3=circuite booleene}}, {{Ill-wd|Q765620|3=mașini Turing cuantice}}, {{Ill-wd|Q1055112|3=circuite monotone}} etc.
* Resursa (sau resursele) care este limitată și limitele: Aceste două proprietăți sunt de obicei exprimate împreună, cum ar fi „timp polinomial”, „spațiu logaritmic”, „adâncime constantă” etc.

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:

: Ansamblul de probleme de decizie rezolvabile de o mașină Turing deterministă în timp ''f''(''n''). (Această clasă de complexitate este cunoscută ca DTIME(''f''(''n'')).)

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 {{Math|{{mset| ''xx'' | ''x'' este orice șir binar}}}} poate fi rezolvat în [[Complexitate în timp|timp 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, {{Ill-wd|Q5138877|3=teza Cobham-Edmonds}} afirmă că „complexitățile în timp în oricare două modele rezonabile și generale de calcul sunt legate polinomial” {{Harvard citation|Goldreich|2008|loc=Chapter 1.2}}. Aceasta formează baza pentru clasa de complexitate [[P (teoria complexității)|P]], 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 este [[FP (clasă de complexitate)|FP]].

=== Clase importante de complexitate ===
[[File:Complexity subsets pspace.svg|thumb|right|Reprezentare a relației între clasele de complexitate; L ar fi un alt pas „înăuntrul” lui NL]]
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:

{| class="wikitable sortable"
! scope=col | Resursă
! scope=col | <abbr title="Mașinii Turing folosite pentru a modela calculul">Determinismul</abbr>
! scope=col | Clasă de complexitate
! scope=col | Constrângere asupra resursei
|-
! scope=rowgroup rowspan=8 style="text-align:center;" | Spațiu
! scope=rowgroup rowspan=4 style="text-align:center;" | Nedeterminist
| {{Ill-wd|Q1756295|3=NSPACE}}(''f''(''n''))
| data-sort-value=0 | O(''f''(''n''))
|-
| {{Ill-wd|Q12857599|3=NL}}
| data-sort-value=1 | O(log ''n'')
|-
| {{Ill-wd|Q500716|3=NPSPACE}}
| data-sort-value=2 | O(poly(''n''))
|-
| {{Ill-wd|Q1141985|3=NEXPSPACE}}
| data-sort-value=4 | O(2<sup>poly(''n'')</sup>)
|-
! scope=rowgroup rowspan=4 style="text-align:center;" | Determinist
| {{Ill-wd|Q1155722|3=DSPACE}}(''f''(''n''))
| data-sort-value=0 | O(''f''(''n''))
|-
| [[L (clasă de complexitate)|L]]
| data-sort-value=1 | O(log ''n'')
|-
| {{Ill-wd|Q500716|3=PSPACE}}
| data-sort-value=2 | O(poly(''n''))
|-
| {{Ill-wd|Q1141985|3=EXPSPACE}}
| data-sort-value=4 | O(2<sup>poly(''n'')</sup>)
|-
! scope=rowgroup rowspan=6 style="text-align:center;" | Timp
! scope=rowgroup rowspan=3 style="text-align:center;" | Nedeterminist
| {{Ill-wd|Q1933581|3=NTIME}}(''f''(''n''))
| data-sort-value=0 | O(''f''(''n''))
|-
| [[NP (teoria complexității)|NP]]
| data-sort-value=2 | O(poly(''n''))
|-
| {{Ill-wd|Q1575791|3=NEXPTIME}}
| data-sort-value=4 | O(2<sup>poly(''n'')</sup>)
|-
! scope=rowgroup rowspan=3 style="text-align:center;" | Determinist
| {{Ill-wd|Q1155831|3=DTIME}}(''f''(''n''))
| data-sort-value=0 | O(''f''(''n''))
|-
| [[P (teoria complexității)|P]]
| data-sort-value=2 | O(poly(''n''))
|-
| {{Ill-wd|Q1276570|3=EXPTIME}}
| data-sort-value=4 | O(2<sup>poly(''n'')</sup>)
|}
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 conform {{Ill-wd|Q954210|3=teoremei lui Savitch}}.

Printre alte clase importante de complexitate se numără {{Ill-wd|Q796890|3=BPP}}, {{Ill-wd|Q136355|3=ZPP}} și {{Ill-wd|Q1190846|3=RP}}, care sunt definite folosind {{Ill-wd|Q1191836|3=mașini Turing probabilistice}}; {{Ill-wd|Q182336|3=AC}} și {{Ill-wd|Q1141840|3=NC}}, care sunt definite folosind circuite booleene; și {{Ill-wd|Q601325|3=BQP}} și {{Ill-wd|Q4047721|3=QMA}}, care sunt definite folosind mașini Turing cuantice. {{Ill-wd|Q1322138|3=#P}} este o clasă importantă de complexitate a problemelor de numărare (nu a problemelor de decizie). Clasele precum {{Ill-wd|Q5973158|3=IP}} și {{Ill-wd|Q4800823|3=AM}} sunt definite utilizând [[Sistem interactiv de dovezi|sisteme de demonstrație interactive]]. {{Ill-wd|Q4652392|3=ALL}} este clasa tuturor problemelor de decizie.

=== Teoreme de ierarhie ===
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(''n''<sup>2</sup>), 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 numesc ''teoreme 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, {{Ill-wd|Q5251122|3=teorema de ierarhie în timp}} afirmă că

: <math>\mathsf{DTIME}\big(f(n) \big) \subsetneq \mathsf{DTIME} \big(f(n) \sdot \log^{2}(f(n)) \big)</math> .

{{Ill-wd|Q7572588|3=Teorema de ierarhie în spațiu}} afirmă că

: <math>\mathsf{DSPACE}\big(f(n)\big) \subsetneq \mathsf{DSPACE} \big(f(n) \sdot \log(f(n)) \big)</math> .

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.

=== Reducere ===
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 pentru ''Y'', atunci ''X'' nu este mai dificil decât ''Y'', și se spune că ''X'' ''se reduce'' la ''Y.'' 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 fi {{Ill-wd|Q2103034|3=reducerile în timp polinomial}} sau {{Ill-wd|Q448582|3=reducerile în spațiu logaritmic}}.

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'' este ''tare'' pentru o clasă de probleme ''C'' dacă orice problemă din ''C'' poate fi redusă la ''X''. Astfel, nicio problemă din ''C'' nu este mai grea decât ''X'', deoarece un algoritm pentru ''X'' ne permite să rezolvăm orice problemă din ''C.'' 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 problemelor [[NP-hard]].

Dacă o problemă ''X'' este în ''C'' și este tare pentru ''C'', atunci se spune că ''X'' este ''{{Ill-wd|Q2532728|3=completă}}'' pentru ''C''. Aceasta înseamnă că ''X'' este cea mai tare problemă din ''C.'' (Deoarece multe probleme ar putea fi la fel de tari, s-ar putea spune că ''X'' este una dintre cele mai tari probleme din ''C''.) Astfel, clasa de probleme [[NP-completitudine|NP-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&nbsp;=&nbsp;NP nu este rezolvată, posibilitatea de a reduce o problemă NP-completă cunoscută, Π<sub>2</sub>, la o altă problemă, Π<sub>1</sub>, ar demonstra că nu există o soluție cunoscută în timp polinomial pentru Π<sub>1</sub>. Aceasta se datorează faptului că o soluție în timp polinomial pentru Π<sub>1</sub> ar da o soluție în timp polinomial pentru Π<sub>2</sub>. Similar, deoarece toate problemele NP pot fi reduse la această mulțime, găsirea unei probleme [[NP-completitudine|NP-complete]] care poate fi rezolvată în timp polinomial ar însemna că P&nbsp;=&nbsp;NP.<ref name="Sipser2006">See {{Harvnb|Sipser|2006|loc=Chapter 7: Time complexity}}</ref>

== Probleme deschise importante ==
[[Fișier:Complexity_classes.svg|miniatura| Diagrama claselor de complexitate cu condiția ca P&nbsp;≠&nbsp;NP. Existența problemelor din NP atât în afara P cât și în afara clasei NP-complete în acest caz a fost stabilită de Ladner.<ref name="Ladner75">{{Citation|last=Ladner|first=Richard E.|title=On the structure of polynomial time reducibility|volume=22|issue=1|pages=151–171|year=1975|postscript=.|periodical={{Ill-wd|Q1709878|3=Journal of the ACM}}|doi=10.1145/321864.321877}}</ref>]]

=== Problema P versus NP ===
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ște {{Ill-wd|Q5138877|3=teza Cobham-Edmonds}}. Pe de altă parte, clasa de complexitate [[NP (teoria complexității)|NP]] 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 fi {{Ill-wd|Q875276|3=problema satisfiabilității booleene}}, [[problema drumului hamiltonian]] și {{Ill-wd|Q11515519|3=problema acoperirii vârfurilor}}. 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.<ref name="Sipser2006"/> 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 de {{Ill-wd|Q6042592|3=programare cu numere întregi}} din {{Ill-wd|Q194292|3=cercetarea operațională}}, multe probleme în [[logistică]], {{Ill-wd|Q899656|3=predicția structurii proteinelor}} în [[biologie]]<ref>{{Citation|last=Berger|first=Bonnie A.|title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete|volume=5|issue=1|pages=27–40|year=1998|postscript=.|periodical=Journal of Computational Biology|citeseerx=10.1.1.139.5547|doi=10.1089/cmb.1998.5.27|pmid=9541869|last2=Leighton|first2=T|author-link=Bonnie Berger|author-link2=F. Thomson Leighton}}</ref> și capacitatea de a găsi dovezi formale ale teoremelor de [[matematică pură]]. <ref>{{Citation|last=Cook|first=Stephen|title=The P versus NP Problem|date=April 2000|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|df=mdy-all|postscript=.|archive-url=https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|publisher={{Ill-wd|Q857975|3=Clay Mathematics Institute}}|access-date=2006-10-18|archive-date=December 12, 2010|author-link=Stephen Cook|url-status=dead}}</ref> Problema P versus NP este una dintre {{Ill-wd|Q727000|3=Problemele Premiului Mileniului}} propuse de {{Ill-wd|Q857975|3=Institutul de Matematică Clay}}. Există un premiu de {{Formatnum|1000000}} de dolari pentru rezolvarea problemei.<ref>{{Citation|last=Jaffe|first=Arthur M.|title=The Millennium Grand Challenge in Mathematics|url=https://www.ams.org/notices/200606/fea-jaffe.pdf|volume=53|issue=6|year=2006|postscript=.|archive-url=https://web.archive.org/web/20060612225513/http://www.ams.org/notices/200606/fea-jaffe.pdf|periodical=Notices of the AMS|access-date=2006-10-18|archive-date=2006-06-12|author-link=Arthur Jaffe|url-status=live}}</ref>

=== Problemele din NP despre care nu se știe dacă sunt P sau NP-complete ===
Ladner a arătat că dacă '''P''' ≠ '''NP''', atunci există probleme în '''NP''' care nu sunt nici '''P''', nici '''NP-complete'''.<ref name="Ladner75"/> Astfel de probleme se numesc probleme {{Ill-wd|Q1130846|3=NP-intermediare}}. {{Ill-wd|Q3738036|3=Problema izomorfismului de grafuri}}, [[Logaritm discret|problema logaritmului discret]] și [[Descompunerea în factori primi|problema 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ă sunt '''P''' sau '''NP-complete'''.

{{Ill-wd|Q3738036|3=Problema izomorfismului de grafuri}} este problema de calcul care cere să se determine dacă două [[Graf|grafuri]] finite sunt {{Ill-wd|Q303100|3=izomorfe}}. O problemă importantă nerezolvată în teoria complexității este dacă problema izomorfismului de grafuri este '''P''', '''NP-completă''' sau NP-intermediară. Răspunsul nu este cunoscut, dar se crede că problema cel puțin nu este NP-completă.<ref name="AK06">{{Citation|last=Arvind|first=Vikraman|title=Graph isomorphism is in SPP|volume=204|issue=5|pages=835–852|year=2006|postscript=.|periodical=Information and Computation|doi=10.1016/j.ic.2006.02.002|last2=Kurur|first2=Piyush P.|doi-access=free}}</ref> Dacă izomorfismul de grafuri este NP-complet, {{Ill-wd|Q2103021|3=ierarhia timpilor polinomiali}} se pliază la al doilea nivel.<ref>{{Citat carte|nume=Schöning|prenume=Uwe|titlu=Stacs 87|legătură-autor=Uwe Schöning|capitol=Graph isomorphism is in the low hierarchy|jurnal=Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science|volum=1987|pagini=114–124|doi=10.1007/bfb0039599|serie=Lecture Notes in Computer Science|an=1987|isbn=978-3-540-17219-2}}</ref> 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 lui {{Ill-wd|Q92845|3=László Babai}} și {{Ill-wd|Q10561835|3=Eugene Luks}}, are timpul de rulare <math>O(2^{\sqrt{n \log n}})</math> pentru grafuri cu ''n'' noduri, deși unele lucrări recente ale lui Babai oferă câteva noi perspective cu potențial în acest sens.

[[Descompunerea în factori primi|Problema factorizării întregilor]] este problema de calcul de determinare a [[Descompunerea în factori primi|descompunerii î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ât ''k''. Nu se cunoaște un algoritm eficient de factorizare a întregilor, iar acest fapt formează baza mai multor sisteme criptografice moderne, cum ar fi algoritmul [[RSA]]. Problema factorizării întregilor este '''NP''' și '''co-NP''' (și chiar în UP și co-UP<ref>{{Citat web|url=http://weblog.fortnow.com/2002/09/complexity-class-of-week-factoring.html|nume=Fortnow|titlu=Computational Complexity Blog: Factoring|date=2002-09-13|first1=Lance|authorlink=Lance Fortnow|lucrare=weblog.fortnow.com}}</ref>). Dacă problema este '''NP-completă''', atunci ierarhia timpilor polinomiali se va plia la primul său nivel (adică, '''NP''' va fi egal cu '''co-NP'''). Cel mai cunoscut algoritm pentru factorizarea întregilor este {{Ill-wd|Q140770|3=ciurul pe corpuri de numere generalizat}}, care necesită un timp de <math>O(e^{\left(\sqrt[3]{\frac{64}{9}}\right)\sqrt[3]{(\log n)}\sqrt[3]{(\log \log n)^2}})</math><ref>Wolfram MathWorld: [http://mathworld.wolfram.com/NumberFieldSieve.html Number Field Sieve]</ref> pentru factorizarea unui număr întreg impar ''n''. Cu toate acestea, cel mai cunoscut {{Ill-wd|Q2623817|3=algoritm cuantic}} pentru această problemă, {{Ill-wd|Q940334|3=algoritmul lui Shor}}, 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ă.

=== Separații între alte clase de complexitate ===
Multe clase de complexitate cunoscute sunt suspectate a fi inegale, dar acest lucru nu a fost demonstrat încă. De exemplu '''P''' ⊆ '''NP''' ⊆ '''{{Ill-wd|Q1563053|3=PP}}''' ⊆ '''PSPACE''', dar este posibil ca '''P''' = '''PSPACE'''. Dacă '''P''' nu este egal cu '''NP''', atunci '''P''' nu este egal nici cu '''PSPACE'''. Deoarece există multe clase de complexitate cunoscute între '''P''' și '''PSPACE''', cum ar fi '''RP''', '''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, '''{{Ill-wd|Q955748|3=Co-NP}}''' este clasa care conține problemele {{Ill-wd|Q4249733|3=complementare}} (adică probleme cu răspunsurile ''da'' / ''nu'' inversate) ale problemelor '''NP'''. Se crede<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> că '''NP''' nu este egal cu '''co-NP''', dar încă nu s-a demonstrat. Este clar că dacă aceste două clase de complexitate nu sunt egale atunci '''P''' nu este egal cu '''NP''', deoarece '''P''' = '''co-P'''. Astfel dacă '''P''' = '''NP''' am avea '''co-P''' = '''co-NP''' de unde '''NP''' = '''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ă în '''P''' sau egală cu '''P'''. Din nou, există multe clase de complexitate între cele două, cum ar fi '''NL''' și '''NC''' și nu se știe dacă sunt clase distincte sau egale.

Se bănuiește că '''P''' și '''BPP''' sunt egale. Cu toate acestea, râmâne în prezent deschisă problema dacă '''BPP''' = '''NEXP'''.

== Netractabilitate ==
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ște '''''{{Visible anchor|problemă netractabilă}}'''''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) {{Ill-wd|Q7486248|3=Introduction to Automata Theory, Languages, and Computation}}, Addison Wesley, Boston/San Francisco/New York (page 368)</ref> În schimb, o problemă care poate fi rezolvată în practică se numește '''''{{Visible anchor|problemă tractabilă}}''''', literalmente „o problemă care poate fi rezolvată”. Termenul ''[[wiktionary:infeasible|nefezabil]]'' (literalmente „care nu se poate face”) este uneori folosit interschimbabil cu ''[[wiktionary:intractable|netractabil]]'',<ref>{{Citat carte|titlu=Algorithms and Complexity|prenume=Gerard|nume=Meurant|an=2014|isbn=978-0-08093391-7|pagină=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4 p. 4]}}</ref> deși acest lucru riscă confuzia cu {{Ill-wd|Q17013331|3=soluțiile fezabile}} din [[Optimizare|optimizarea matematică]].<ref>
{{Citat carte|titlu=Writing for Computer Science|prenume=Justin|nume=Zobel|pagină=[https://books.google.com/books?id=LWCYBgAAQBAJ&pg=PA132 132]|an=2015|isbn=978-1-44716639-9}}</ref>

Problemele tractabile sunt frecvent identificate cu probleme care au soluții în timp polinomial ('''P''', '''PTIME'''); aceasta este {{Ill-wd|Q5138877|3=teza Cobham-Edmonds}}. Problemele despre care se știe că sunt netractabile în acest sens le includ și pe cele care sunt dure {{Ill-wd|Q1276570|3=EXPTIME}}. Dacă NP nu este același cu P, atunci problemele [[NP-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 din [[aritmetica 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 rezolva [[problema rucsacului]] (care este NP-completă) pe o gamă largă de dimensiuni în timp mai rapid decât cel pătratic, iar {{Ill-wd|Q21055608|3=rezolvitoarele SAT}} gestionează în mod obișnuit cazuri mari ale {{Ill-wd|Q875276|3=problemei satisfiabilității booleene}}, 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 2<sup>''n''</sup> operațiuni înainte de a se opri. Pentru un ''n'' mic, cum ar fi 100, și presupunând, de dragul exemplului, că calculatorul efectuează 10<sup>12</sup> operații în fiecare secundă, programul ar rula timp de aproximativ 4&nbsp;×&nbsp;10<sup>10</sup> ani, același ordin de mărime ca [[vâ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,0001<sup>''n''</sup> operații este practic până când ''n'' 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, ''n''<sup>15</sup>, 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 ordinul ''n''<sup>3</sup> sau ''n''<sup>2</sup> sunt adesea nepractici pentru dimensiuni realiste ale problemelor.

== Teoria complexității continue ==
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 de [[Analiză numerică|analiza numerică]]. O abordare a teoriei complexității analizei numerice<ref>{{Citat revistă|nume=Smale|prenume=Steve|an=1997|titlu=Complexity Theory and Numerical Analysis|journal=Acta Numerica|volum=6|pagini=523–551|publisher=Cambridge Univ Press|bibcode=1997AcNum...6..523S|doi=10.1017/s0962492900002774}}</ref> este {{Ill-wd|Q6030626|3=complexitatea bazată pe informații}}.

Teoria complexității continue se poate referi și la teoria complexității utilizării [[Calculator analogic|calculului analogic]], care utilizează [[Sistem dinamic|sisteme dinamice]] continue și [[Ecuație diferențială|ecuații diferențiale]]. {{Ill-wd|Q6501221|3=Teoria controlului}} 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.<ref>{{Citat revistă|nume=Tomlin|nume2=Mitchell|nume3=Bayen|nume4=Oishi|prenume=Claire J.|prenume2=Ian|prenume3=Alexandre M.|prenume4=Meeko|legătură-autor4=Meeko Oishi|dată=July 2003|titlu=Computational Techniques for the Verification of Hybrid Systems|journal=Proceedings of the IEEE|volum=91|număr=7|pagini=986–1001|doi=10.1109/jproc.2003.814621}}</ref>

== Istorie ==
Unul din primele exemple de analiză a complexității algoritmilor este analiza timpului de rulare a [[Algoritmul lui Euclid|algoritmului lui Euclid]] realizată de [[Gabriel 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ătre [[Alan 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 „{{Lang|en|On the Computational Complexity of Algorithms|italic=nu}}” (lit. „Despre complexitatea computațională a algoritmilor”) de [[Juris Hartmanis]] și [[Richard Stearns|Richard E. Stearns]], care a stabilit definițiile [[Complexitate în timp|complexității în timp]] și {{Ill-wd|Q2098905|3=complexității în spațiu}} și a demonstrat teoremele ierarhiei. În plus, în 1965, [[Jack Edmonds|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.<ref>Richard M. Karp, "[http://cecas.clemson.edu/~shierd/Shier/MthSc816/turing-karp.pdf Combinatorics, Complexity, and Randomness]", 1985 Turing Award Lecture</ref>

Printre primele lucrări care au studiat problemele rezolvabile de mașinile Turing cu resurse limitate specifice se numără definiția dată de {{Ill-wd|Q402579|3=John Myhill}} {{Ill-wd|Q1149323|3=automatelor liniare mărginite}} (Myhill 1960), studiul mulțimilor rudimentare al lui [[Raymond Smullyan]] (1961), precum și lucrarea lui {{Ill-wd|Q5772337|3=Hisao Yamada}}<ref>{{Citat revistă|nume=Yamada|prenume=H.|an=1962|titlu=Real-Time Computation and Recursive Functions Not Real-Time Computable|journal=IEEE Transactions on Electronic Computers|volum=EC-11|număr=6|pagini=753–760|doi=10.1109/TEC.1962.5219459}}</ref> despre calculul în timp real (1962). Ceva mai devreme, [[Boris Trahtenbrot|Boris Trakhtenbrot]] (1956), un pionier al domeniului din URSS, a studiat o altă măsură specifică a complexității.<ref>Trakhtenbrot, B.A.: Signalizing functions and tabular operators. Uchionnye Zapiski
Penzenskogo Pedinstituta (Transactions of the Penza Pedagogoical Institute) 4, 75–87 (1956) (in Russian)</ref> El își amintește:
{{Citat|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 din {{Ill-wd|Q7659118|3=teoria comutației}}, 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».<ref>Boris Trakhtenbrot, "{{Google books|GFX2qiLuRAMC|page=1|plainurl=yes}} From Logic to Theoretical Computer Science – An Update]". În: ''Pillars of Computer Science'', LNCS 4800, Springer 2008.</ref>}}
În 1967, Manuel Blum a formulat un set de axiome (numite astăzi {{Ill-wd|Q4059945|3=axiomele lui Blum}}) care specificau proprietățile dorite ale măsurilor complexității pe mulțimea funcțiilor calculabile și a demonstrat un rezultat important, așa numita {{Ill-wd|Q1751105|3=teoremă a accelerării}}. Domeniul a început să înflorească în 1971 când [[Stephen Cook]] și {{Ill-wd|Q92966|3=Leonid Levin}} {{Ill-wd|Q377276|3=au demonstrat}} existența problemelor cu relevanță practică care sunt [[NP-completitudine|NP-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 de [[combinatorică]] și [[teoria grafurilor]], fiecare cunoscută pentru netractabilitatea lor computațională, sunt NP-complete.

== Note ==
<references/>

== Bibliografie ==

=== Manuale ===

* {{Citation|last=Arora|first=Sanjeev|title=Computational Complexity: A Modern Approach|url=http://www.cs.princeton.edu/theory/complexity/|year=2009|publisher=Cambridge University Press|isbn=978-0-521-42426-4|zbl=1193.68112|last2=Barak|first2=Boaz|author-link=Sanjeev Arora}}
* {{Citation|last=Downey|first=Rod|title=Parameterized complexity|url=https://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html|year=1999|series=Monographs in Computer Science|place=Berlin, New York|publisher=Springer-Verlag|isbn=9780387948836|last2=Fellows|first2=Michael|author-link2=Michael Fellows}} 
* {{Citation|last=Du|first=Ding-Zhu|title=Theory of Computational Complexity|year=2000|publisher=John Wiley & Sons|isbn=978-0-471-34506-0|last2=Ko, Ker-I}}
* {{Garey-Johnson}}
* {{Citation|last=Goldreich|first=Oded|title=Computational Complexity: A Conceptual Perspective|url=http://www.wisdom.weizmann.ac.il/~oded/cc-book.html|year=2008|publisher=Cambridge University Press|author-link=Oded Goldreich}}
* {{Citation|title=Handbook of theoretical computer science (vol. A): algorithms and complexity|year=1990|editor-last=van Leeuwen|editor-first=Jan|publisher=MIT Press|isbn=978-0-444-88071-0|editor1-link=Jan van Leeuwen}}
* {{Citation|last=Papadimitriou|first=Christos|title=Computational Complexity|year=1994|edition=1st|publisher=Addison Wesley|isbn=978-0-201-53082-7|author-link=Christos Papadimitriou}}
* {{Citation|last=Sipser|first=Michael|title=Introduction to the Theory of Computation|year=2006|edition=2nd|place=USA|publisher=Thomson Course Technology|isbn=978-0-534-95097-2|author-link=Michael Sipser}}

=== Studii ===

* {{Citation|last=Khalil|first=Hatem|title=A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations|url=http://portal.acm.org/citation.cfm?id=800191.805573|pages=197–201|year=1976|series=ACM '76|periodical=Proceedings of the Annual Conference on - ACM 76|doi=10.1145/800191.805573|isbn=9781450374897|last2=Ulery|first2=Dana|author-link2=Dana Ulery}}
* {{Citation|last=Cook|first=Stephen|title=An overview of computational complexity|volume=26|issue=6|pages=400–408|year=1983|periodical=Commun. ACM|doi=10.1145/358141.358144|issn=0001-0782|author-link=Stephen Cook|doi-access=free}}
* {{Citation|last=Fortnow|first=Lance|title=A Short History of Computational Complexity|url=http://people.cs.uchicago.edu/~fortnow/papers/history.pdf|volume=80|pages=95–133|year=2003|periodical=Bulletin of the EATCS|last2=Homer|first2=Steven}}
* {{Citation|last=Mertens|first=Stephan|title=Computational Complexity for Physicists|volume=4|issue=3|pages=31–47|year=2002|periodical=Computing in Science and Eng.|arxiv=cond-mat/0012185|bibcode=2002CSE.....4c..31M|doi=10.1109/5992.998639|issn=1521-9615}}

== Legături externe ==
{{Commonscat}}
* [https://complexityzoo.net/Complexity_Zoo Complexity Zoo:]
* {{springer|title=Computational complexity classes|id=p/c130160}}
* [https://mathoverflow.net/q/34487 Care sunt cele mai importante rezultate (și lucrări) în teoria complexității pe care fiecare ar trebui să le cunoască?]
* [https://www.scottaaronson.com/papers/philos.pdf Scott Aaronson: De ce filozofilor ar trebui să le pese de complexitatea computațională]
{{Control de autoritate}}
[[Categorie:Teoria complexității de calcul]]
[[Categorie:Pagini cu traduceri nerevizuite]]