Portada	Favoritos
Lista Articulos: [0-C] [C-I] [I-P] [P-Z] | Todas las categorías | Página aleatoria | Lo que enlaza aquí

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)

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:

• Lista de clases de complejidad