Clase de complejidad

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada.

Una clase de complejidad tiene una definición de la forma:

el conjunto de los problemas de decisión que pueden ser resueltos por una máquina M utilizando O(f(n)) del recurso R (donde n es el tamaño de la entrada).

Relación entre las principales clases de complejidad[editar]

La siguiente tabla muestra algunas de las clases de problemas (o lenguajes o gramáticas) que se consideran en teoría de la complejidad computacional. Cuando la clase X es un subconjunto estricto de Y, X aparece en la tabla bajo Y con una línea sólida uniéndolos. Cuando es subconjunto pero no se sabe si es estricto, la línea es cortada y gris. Técnicamente hablando, el corte entre problemas decidibles e indecidibles es tema de la Teoría de la computabilidad, pero resulta interesante mencionarlos aquí para poner en perspectiva las clases de complejidad

Problema de decisión
SolidLine.png SolidLine.png
Lenguaje recursivo enumerable
Problema indecidible
SolidLine.png
Problema decidible
SolidLine.png
ESPACIOEXP
DottedLine.png
TIEMPOEXP
DottedLine.png
ESPACIOP
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
Gramática sensitiva al contexto
SolidLine.png DottedLine.png DottedLine.png DottedLine.png
ESPACIOP-completo
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
Co-NP
DottedLine.png
NP
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png DottedLine.png
BPP
BQP
NP-completo
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
P
SolidLine.png SolidLine.png DottedLine.png DottedLine.png
SolidLine.png
NC
P-completo
SolidLine.png SolidLine.png
Gramática libre de contexto
SolidLine.png
Gramática regular

Ejemplos[editar]

Véase también[editar]