În și matematică, teoria complexității se concentrează pe clasificarea î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 pentru a studia aceste probleme și cuantificând , 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 ), numărul de porți dintr-un circuit (utilizat în ) ș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 , este dedicată domeniului complexității computaționale.
În informatica teoretică, acest domeniu este în strânsă legătură cu ș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
Instanțe de probleme O 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 . 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 . 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
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 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 este o problemă de calcul în care pentru fiecare intrare se așteaptă o singură ieșire (a unei ), dar rezultatul este mai complex decât cel al unei probleme de decizie 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. 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
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 , Jocul Vieții al lui Conway, automate celulare, 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 nedeterministe, , și . 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 . 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 , cum ar fi . 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.See Ceea ce au în comun toate aceste modele este că mașinile funcționează .
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 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 dacă timpul necesar lui M pentru fiecare intrare de lungime este cel mult . O problemă de decizie A poate fi rezolvată în timp dacă există o mașină Turing care rezolvă problema în timp . 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 pe o mașină Turing deterministă este notat cu ().