NL (clase de complejidad)


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 tamaño de la entrada, por una máquina de Turing no determinista tal que la solución si existe es única. La clase L está contenida en NL y está contenida estrictamente en PSPACE. Como NL también está contenida estrictamente en PSPACE, se concluye que en la relación

L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE
P es diferente de NP o bien NP es diferente de PSPACE, pero no se sabe cual de las dos inclusiones es propia.

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 …   Wikipedia Español

  • 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

  • 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”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.