Classe de complexitat

En teoria de complexitat computacional, conjunt de problemes relacionats pels recursos computacionals requerits per resoldre'ls

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ó
   
Tipus 0 (Enumerable recursivament)
Indecidible
 
Decidible
 
EXPSPACE
 
NEXPTIME
 
EXPTIME
 
PSPACE
         
Tipus 1 (Sensible al context)
       
         
   
co-NP
BQP
NP
         
     
BPP
 
         
   
P
     
 
NC
   
Tipus 2 (Lliure de context)
 
Tipus 3 (Gramàtica regular)

Referències modifica

  1. «Computational Complexity Theory», 16-04-2016. Arxivat de l'original el 2016-04-16. [Consulta: 28 novembre 2018].
  2. Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790.