PP (clase de complejidad)

PP (clase de complejidad)

En teoría de la complejidad computacional PP, que quiere decir tiempo polinomial probabilístico, es una clase de problema de decisión, resoluble por una máquina de Turing probabilística, diferente de la máquina de Turing general o determinística en que las transiciones entre estados tienen la misma probabilidad de ocurrencia.


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

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