Clase de complejidad

Clase de complejidad

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

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

  • La clase NP es el conjunto de problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista.
  • La clase PSPACE es el conjunto de problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinómico.

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Clase de complejidad — 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 …   Enciclopedia Universal

  • P (clase de complejidad) — Se ha sugerido que este artículo o sección sea fusionado con Tiempo polinómico (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí …   Wikipedia Español

  • NC (clase de complejidad) — En teoría de la complejidad computacional, la clase de complejidad NC (la clase de Nick) es el conjunto de los problemas de decisión que pueden ser resueltos mediante computación paralela con un número polinómico de procesadores en tiempo… …   Wikipedia Español

  • RE (clase de complejidad) — En complejidad computacional, RE (abreviación de recursivamente enumerable) es la clase de complejidad conformada por aquellos problemas de decisión para los cuales una respuesta sí puede ser verificada por una máquina de Turing en una cantidad… …   Wikipedia Español

  • L (clase de complejidad) — En teoría de la complejidad computacional, la clase de complejidad L (LSPACE o espacio logarítmico determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n… …   Wikipedia Español

  • PH (clase de complejidad) — Para otros usos del término PH, véase la página de desambiguación. En teoría de la complejidad computacional, la clase de complejidad PH es la unión de todas las clases de complejidad de la jerarquía polinómica. (Tiempo y espacio) PH está… …   Wikipedia Español

  • ALL (clase de complejidad) — En complejidad computacional, ALL es la clase de complejidad conformada por todos los problemas de decisión. Relaciones con otras clases ALL contiene todas las clases de complejidad de problemas de decisión, incluyendo las clases RE y co RE.… …   Wikipedia Español

  • PH (clase de complejidad) — Para otros usos del término PH, véase la página de desambiguación. En teoría de la complejidad computacional, la clase de complejidad PH es la unión de todas las clase de complejidad de la jerarquía polinómica. PH está contenida en las clases… …   Enciclopedia Universal

  • NL (clase de complejidad) — En teoría de la complejidad computacional, la clase de complejidad NL (espacio logarítmico no determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el …   Wikipedia Español

  • UP (clase de complejidad) — En teoría de la complejidad computacional, la clase de complejidad UP (tiempo polinómico, no determinista, no ambiguo) es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”