Teoria complexității
dificultatea inerentă a problemelor de calcul / From Wikipedia, the free encyclopedia
Î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.[1]
Î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.