În teoria algoritmilor , clasele de complexitate sunt seturi de probleme de calcul care sunt aproximativ aceleași în ceea ce privește complexitatea de calcul. Mai restrâns, clasele de complexitate sunt seturi de predicate ( funcții care iau un cuvânt ca intrare și returnează un răspuns de 0 sau 1) care folosesc aproximativ aceeași cantitate de resurse pentru a calcula.
Pentru fiecare clasă, există o categorie de sarcini care sunt „cele mai dificile” din clasa respectivă. Aceasta înseamnă că orice sarcină dintr-o clasă este redusă la o astfel de sarcină și, în plus, sarcina în sine se află în clasă. Astfel de sarcini sunt numite sarcini complete ( ing. -complete ) pentru o anumită clasă. Cea mai cunoscută problemă completă este problema NP-completă .
Problemele complete sunt un instrument convenabil pentru a demonstra egalitatea de clasă. Este suficient ca o astfel de problemă să ofere un algoritm care să o rezolve și să aparțină unei clase mai mici, iar egalitatea va fi demonstrată.
Fiecare clasă de complexitate (în sens restrâns) este definită ca un set de predicate care au anumite proprietăți. O definiție tipică a unei clase de complexitate arată astfel:
O clasă de complexitate X este un set de predicate P(x) care sunt calculabile pe mașinile Turing și utilizează o resursă O (f(n)) pentru a calcula, unde n este lungimea cuvântului x .Resursele sunt de obicei luate ca timp de calcul (numărul de cicluri de lucru ale mașinii Turing) sau zona de lucru (numărul de celule utilizate pe bandă în timpul funcționării). Limbile recunoscute prin predicate dintr-o anumită clasă (adică setul de cuvinte pentru care predicatul returnează 1) se spune, de asemenea, că aparțin aceleiași clase.
În plus, multe clase pot fi descrise și în termeni de logică matematică sau teoria jocurilor .
Clasele sunt de obicei notate cu majuscule. Complementul la clasa C (adică clasa de limbi ale căror complemente aparțin lui C ) se notează co-C .
Toate clasele de complexitate sunt într-o relație ierarhică: unele le includ pe altele. Cu toate acestea, pentru majoritatea incluziunilor, nu se știe dacă sunt stricte. Una dintre cele mai cunoscute probleme deschise din acest domeniu este egalitatea claselor P și NP . Dacă această presupunere este corectă (de care mulți oameni de știință se îndoiesc), atunci ierarhia de clasă afișată în dreapta va fi puternic prăbușită. În momentul de față, cea mai comună ipoteză este că ierarhia este nedegenerată (adică toate clasele sunt diferite). În plus, se știe cu siguranță că EXPSPACE nu este egal cu clasa PSPACE .
Se consideră o funcție f și un șir de intrare de lungime n . Atunci clasa DTIME (f(n)) este definită ca clasa de limbaje acceptată de mașinile Turing deterministe care își termină munca în timp care nu depășește f(n) . Clasa NTIME (f(n)) , la rândul său, este definită ca clasa de limbaje acceptată de o mașină Turing nedeterministă care își finalizează activitatea în timp care nu depășește f(n) . Rețineți că nu există restricții de memorie atunci când definiți aceste clase.
Similar cu ierarhia de timp, este introdusă o ierarhie de memorie. Clasa DSPACE (f(n)) desemnează o clasă de limbaje acceptată de mașinile Turing deterministe care utilizează cel mult f(n) locații de memorie pe benzile de lucru. Clasa NSPACE (f(n)) este definită ca o clasă de limbaje acceptată de mașinile Turing nedeterministe care utilizează cel mult locații de memorie f(n) pe benzile de lucru. Nu există limite de timp la definirea acestor clase.
Alte clase similare considerate mai sus sunt definite în mod similar. Iată abrevierile folosite:
| Clasele de complexitate ale algoritmilor | |
|---|---|
| Considerată ușoară | |
| Ar trebui să fie dificil | |
| Considerat dificil |
|