En teoria de complexitat, una classe de complexitat és un conjunt de problemes de decisió de complexitat relacionada. Una classe de complexitat típica té una definició de la forma:
El conjunt de problemes que se poden resoldre per una màquina abstracta M usant O (f(n)) del recurs R on n és la mida de l'entrada.
Les classes de complexitat estan relacionades amb la taxa de creixement de la necessitat de recursos a mesura que augmenta l'entrada n. És una mesura abstracta i no dona uns requeriments de temps o espai en termes de segons o bytes, ja que per obtenir-los caldria tenir informació de la implementació concreta. La funció dins de l'expressió O(...) pot ser una constant, per algorismes que no els afecta la mida n, o una expressió amb un logaritme, una potència d'n com una expressió polinomial o moltes d'altres. La O es llegeix com "d'ordre ". Pel propòsit de teoria de la complexitat, alguns detalls de la funció es poden ignorar, per exemple diferents expressions polinomials es poden ajuntar en una sola classe.
El recurs en qüestió pot ser temps, essencialment el nombre d'operacions bàsiques que ha de realitzar una màquina abstracta o espai (emmagatzemament). Per exemple, la classe NP és el conjunt de problemes de decisió les solucions dels quals es poden comprovar per una màquina de Turing no determinista en un temps polinomial, mentre que la classe PSPACE és el conjunt de problemes que es poden solucionar per una màquina de Turing determinista en un espai polinomial.
Relacions entre les principals classes de complexitat
[modifica]La següent taula mostra les principals classes de problemes o de llenguatges o gramàtiques consideres en teoria de la complexitat. si una classe X és un subconjunt estricte d'Y, llavors X es mostra sota d'Y amb una línia sòlida unint-les. Si X és un subconjunt però no es coneix si és estricte, la línia és gris i puntejada.[1][2]
|
|---|
| Considerades tractables | |
|---|
| Suposadament intractables | |
|---|
| Considerades intractables | |
|---|
| Jerarquia de classes | |
|---|
| Families de classes | |
|---|
