Teoria complexității

În informatica teoretică^⁠(d) și matematică, teoria complexității se concentrează pe clasificarea problemelor 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 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 modele matematice de calcul^⁠(d) pentru a studia aceste probleme și cuantificând complexitatea 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ă în complexitatea comunicațiilor^⁠(d)), numărul de porți dintr-un circuit (utilizat în complexitatea circuitelor^⁠(d)) și numărul de procesoare (utilizate în calculul 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 șapte probleme ale Premiului Mileniului^⁠(d), este dedicată domeniului complexității computaționale.

În informatica teoretică, acest domeniu este în strânsă legătură cu analiza algoritmilor^⁠(d) ș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

Turul unui comis-voiajor prin 14 orașe germane.

Instanțe de probleme

O problemă de calcul^⁠(d) 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 testului 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, 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 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 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. 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-un computer 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 în notație binară, iar grafurile pot fi codificate direct prin matricele lor de adiacență sau prin codificarea 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

O problemă de decizie^⁠(d) are doar două ieșiri posibile, da sau nu (sau 1 sau 0) oricare ar fi intrarea.

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 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 conex. 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.

Probleme funcție

O problemă funcție^⁠(d) este o problemă de calcul în care pentru fiecare intrare se așteaptă o singură ieșire (a unei funcții totale^⁠(d)), dar rezultatul este mai complex decât cel al unei probleme de decizie^⁠(d) — adică rezultatul nu este doar da sau nu. Printre cele mai emblematice exemple se numără problema comis-voiajorului și 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, b, c) astfel încât să fie valabilă relația a × b = 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 2n 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 î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.

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

Mașina Turing

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 — 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 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 maș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 fi mașini Turing deterministe, mașini Turing probabilistice^⁠(d), mașini Turing nedeterministe^⁠(d), mașini Turing cuantice^⁠(d), mașini Turing simetrice^⁠(d) și maș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ți algoritmi 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.

Alte modele de mașini

În literatura de specialitate, au apărut multe propuneri de modele de mașini diferite de mașinile Turing standard cu bandă multiplă^⁠(d), cum ar fi maș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. 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ât timpul nedeterminist^⁠(d) 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ș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 f(n) dacă timpul necesar lui M pentru fiecare intrare de lungime n este cel mult f(n). O problemă de decizie A poate fi rezolvată în timp f(n) dacă există o mașină Turing care rezolvă problema în timp 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 f(n) pe o mașină Turing deterministă este notat cu DTIME^⁠(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, orice măsură a complexității^⁠(d) poate fi privită ca o resursă de calcul. Măsurile complexității sunt foarte general definite de axiomele 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) și complexitatea arborelui de decizie^⁠(d).

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

Complexitatea în cazul cel mai bun, cel mai rău și mediu

Vizualizare a algoritmului quicksort care are performanța în cazul mediu^⁠(d) ${\mathcal {O}}(n\log n)$.

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 dimensiunea n pot fi mai rapid de rezolvat decât altele, definim următoarele complexități:

1. Complexitatea în cel mai bun caz: Aceasta este complexitatea rezolvării problemei pentru cea mai bună intrare de dimensiune n.
2. Complexitatea medie a cazului: Aceasta este complexitatea rezolvării problemei în medie. Această complexitate este definită doar în raport cu o 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.
3. Analiza amortizată^⁠(d) 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.
4. 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 distribuție uniformă discretă^⁠(d)), 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ă O(n²). Dacă presupunem că toate permutările posibile ale listei de intrare sunt la fel de probabile, timpul mediu necesar pentru sortare este 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 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 analizei 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 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) = 7n² + 15n + 40, în notația Big O s-ar scrie T(n) = O(n²).

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 problemelor funcție^⁠(d), problemelor de numărare^⁠(d), problemelor de optimizare^⁠(d), problemelor de promisiuni^⁠(d) 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, circuite booleene^⁠(d), mașini Turing cuantice^⁠(d), circuite monotone^⁠(d) 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 { xx | x este orice șir binar} poate fi rezolvat în 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, 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 complexitate 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.

Clase importante de complexitate

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:

Resursă	Determinismul	Clasă de complexitate	Constrângere asupra resursei
Spațiu	Nedeterminist	NSPACE⁠(d)(f(n))	O(f(n))
		NL⁠(d)	O(log n)
		NPSPACE⁠(d)	O(poly(n))
		NEXPSPACE⁠(d)	O(2poly(n))
	Determinist	DSPACE⁠(d)(f(n))	O(f(n))
		L	O(log n)
		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 conform teoremei lui Savitch^⁠(d).

Printre alte clase importante de complexitate se numără BPP^⁠(d), ZPP^⁠(d) și RP^⁠(d), care sunt definite folosind mașini Turing probabilistice^⁠(d); AC^⁠(d) și NC^⁠(d), care sunt definite folosind circuite booleene; și BQP^⁠(d) și QMA^⁠(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 precum IP^⁠(d) și AM^⁠(d) sunt definite utilizând sisteme de demonstrație interactive. ALL^⁠(d) 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²), 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, teorema de ierarhie în timp^⁠(d) afirmă că

${\mathsf {DTIME}}{\big (}f(n){\big )}\subsetneq {\mathsf {DTIME}}{\big (}f(n)\cdot \log ^{2}(f(n)){\big )}$ .

Teorema de ierarhie în spațiu^⁠(d) afirmă că

${\mathsf {DSPACE}}{\big (}f(n){\big )}\subsetneq {\mathsf {DSPACE}}{\big (}f(n)\cdot \log(f(n)){\big )}$ .

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 reducerile în timp polinomial^⁠(d) sau reducerile î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 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 completă^⁠(d) 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-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ă, Π₂, la o altă problemă, Π₁, ar demonstra că nu există o soluție cunoscută în timp polinomial pentru Π₁. Aceasta se datorează faptului că o soluție în timp polinomial pentru Π₁ ar da o soluție în timp polinomial pentru Π₂. Similar, deoarece toate problemele NP pot fi reduse la această mulțime, găsirea unei probleme NP-complete care poate fi rezolvată în timp polinomial ar însemna că P = NP.

Probleme deschise importante

Diagrama claselor de complexitate cu condiția ca P ≠ 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.

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 teza Cobham-Edmonds^⁠(d). Pe de altă parte, clasa de complexitate 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 problema satisfiabilității booleene^⁠(d), problema drumului hamiltonian și problema 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. 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 programare cu numere întregi^⁠(d) din cercetarea operațională^⁠(d), multe probleme în logistică, predicția structurii proteinelor^⁠(d) în biologie și capacitatea de a găsi dovezi formale ale teoremelor de matematică pură. Problema P versus NP este una dintre Problemele Premiului Mileniului^⁠(d) propuse de Institutul de Matematică Clay^⁠(d). Există un premiu de 1.000.000 de dolari pentru rezolvarea problemei.

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. Astfel de probleme se numesc probleme NP-intermediare^⁠(d). Problema izomorfismului de grafuri^⁠(d), problema logaritmului discret și 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.

Problema izomorfismului de grafuri^⁠(d) este problema de calcul care cere să se determine dacă două grafuri finite sunt izomorfe^⁠(d). 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ă. Dacă izomorfismul de grafuri este NP-complet, ierarhia timpilor polinomiali^⁠(d) se pliază la al doilea nivel. 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 László Babai^⁠(d) și Eugene Luks^⁠(d), are timpul de rulare $O(2^{\sqrt {n\log n}})$ 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.

Problema factorizării întregilor este problema de calcul de determinare a 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). 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 ciurul pe corpuri de numere generalizat^⁠(d), care necesită un timp de $O(e^{\left({\sqrt[{3}]{\frac {64}{9}}}\right){\sqrt[{3}]{(\log n)}}{\sqrt[{3}]{(\log \log n)^{2}}}})$ pentru factorizarea unui număr întreg impar n. Cu toate acestea, cel mai cunoscut algoritm 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ă.

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 ⊆ PP^⁠(d) ⊆ 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, Co-NP^⁠(d) este clasa care conține problemele complementare^⁠(d) (adică probleme cu răspunsurile da / nu inversate) ale problemelor NP. Se crede 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 problemă netractabilă. În schimb, o problemă care poate fi rezolvată în practică se numește problemă tractabilă, literalmente „o problemă care poate fi rezolvată”. Termenul nefezabil (literalmente „care nu se poate face”) este uneori folosit interschimbabil cu netractabil, deși acest lucru riscă confuzia cu soluțiile fezabile^⁠(d) din optimizarea matematică.

Problemele tractabile sunt frecvent identificate cu probleme care au soluții în timp polinomial (P, PTIME); aceasta este teza Cobham-Edmonds^⁠(d). Problemele despre care se știe că sunt netractabile în acest sens le includ și pe cele care sunt dure EXPTIME^⁠(d). 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 rezolvitoarele SAT^⁠(d) gestionează în mod obișnuit cazuri mari ale problemei 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 2ⁿ 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¹² operații în fiecare secundă, programul ar rula timp de aproximativ 4 × 10¹⁰ 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ⁿ 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¹⁵, 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³ sau n² 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 analiza numerică. O abordare a teoriei complexității analizei numerice este complexitatea bazată pe informații^⁠(d).

Teoria complexității continue se poate referi și la teoria complexității utilizării calculului analogic, care utilizează sisteme dinamice continue și ecuaț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.

Istorie

Unul din primele exemple de analiză a complexității algoritmilor este analiza timpului de rulare a 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 „On the Computational Complexity of Algorithms” (lit. „Despre complexitatea computațională a algoritmilor”) de Juris Hartmanis și Richard E. Stearns, care a stabilit definițiile complexității în timp și complexităț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.

Printre primele lucrări care au studiat problemele rezolvabile de mașinile Turing cu resurse limitate specifice se numără definiția dată de John Myhill^⁠(d) automatelor liniare mărginite^⁠(d) (Myhill 1960), studiul mulțimilor rudimentare al lui Raymond Smullyan (1961), precum și lucrarea lui Hisao Yamada^⁠(d) 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. 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 din teoria 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».”

În 1967, Manuel Blum a formulat un set de axiome (numite astăzi axiomele 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 numita teoremă a accelerării^⁠(d). Domeniul a început să înflorească în 1971 când Stephen Cook și Leonid Levin^⁠(d) au demonstrat^⁠(d) existența problemelor cu relevanță practică care sunt 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.

Bibliografie

Manuale

• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112 
• Downey, Rod; Fellows, Michael (1999), Parameterized complexity, Monographs in Computer Science, Berlin, New York: Springer-Verlag, ISBN 9780387948836  
• Du, Ding-Zhu; Ko, Ker-I (2000), Theory of Computational Complexity, John Wiley & Sons, ISBN 978-0-471-34506-0 
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5 
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press 
• van Leeuwen, Jan, ed. (1990), Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, ISBN 978-0-444-88071-0 
• Papadimitriou, Christos (1994), Computational Complexity (ed. 1st), Addison Wesley, ISBN 978-0-201-53082-7 
• Sipser, Michael (2006), Introduction to the Theory of Computation (ed. 2nd), USA: Thomson Course Technology, ISBN 978-0-534-95097-2 

Studii

• Khalil, Hatem; Ulery, Dana (1976), „A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations”, Proceedings of the Annual Conference on - ACM 76, ACM '76, pp. 197–201, doi:10.1145/800191.805573, ISBN 9781450374897 
• Cook, Stephen (1983), „An overview of computational complexity”, Commun. ACM, 26 (6), pp. 400–408, doi:10.1145/358141.358144 , ISSN 0001-0782 
• Fortnow, Lance; Homer, Steven (2003), „A Short History of Computational Complexity” (PDF), Bulletin of the EATCS, 80, pp. 95–133 
• Mertens, Stephan (2002), „Computational Complexity for Physicists”, Computing in Science and Eng., 4 (3), pp. 31–47, arXiv:cond-mat/0012185 , Bibcode:2002CSE.....4c..31M, doi:10.1109/5992.998639, ISSN 1521-9615 

Legături externe

• Complexity Zoo:
• Hazewinkel, Michiel, ed. (2001), „Computational complexity classes”, Encyclopaedia of Mathematics, Kluwer Academic Publishers, ISBN 978-1556080104 
• Care sunt cele mai importante rezultate (și lucrări) în teoria complexității pe care fiecare ar trebui să le cunoască?
• Scott Aaronson: De ce filozofilor ar trebui să le pese de complexitatea computațională