Classe de complexitat

De Viquipèdia
Salta a la navegació Salta a la cerca

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]

Problema de decisió
SolidLine.png SolidLine.png
Tipus 0 (Enumerable recursivament)
Indecidible
SolidLine.png
Decidible
SolidLine.png
EXPSPACE
DottedLine.png
NEXPTIME
DottedLine.png
EXPTIME
DottedLine.png
PSPACE
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
Tipus 1 (Sensible al context)
SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
co-NP
BQP
NP
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png DottedLine.png
BPP
DottedLine.png
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
P
SolidLine.png SolidLine.png DottedLine.png
SolidLine.png
NC
SolidLine.png SolidLine.png
Tipus 2 (Lliure de context)
SolidLine.png
Tipus 3 (Gramàtica regular)

Referències[modifica]

  1. «Computational Complexity Theory», 16-04-2016. [Consulta: 28 novembre 2018].
  2. Michael., Sipser,. Introduction to the theory of computation. 3rd ed. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.