En la teoría de complejidad, el PP es la clase de los problemas de decisión solubles por una máquina de probabilidad de Turing en tiempo polinómico, con una probabilidad de error de menos el de 1/2 para todos los casos. El PP de la abreviatura refiere a tiempo polinómico de probabilidad. La clase de la complejidad fue definida por Gill en 1977.
Si un problema de decisión está en el PP, después hay un algoritmo para él que se permita mover de un tirón monedas y tomar decisiones al azar. Se garantiza para funcionar en tiempo polinómico. Si la respuesta está SÍ, el algoritmo contestará SÍ con la probabilidad más el de 1/2. Si la respuesta es NO, el algoritmo contestará SÍ con probabilidad el inferior o igual 1/2. En términos más prácticos, es la clase de problemas que se puedan solucionar a cualquier grado de exactitud fijo funcionando haber seleccionado al azar, algoritmo del polinómico-tiempo un número suficiente (pero ilimitado) de épocas.
Una caracterización alternativa del PP es el sistema de los problemas que se pueden solucionar por una máquina no determinista de Turing en tiempo polinómico donde está la condición de la aceptación que una mayoría (más que medio) de trayectorias del cómputo acepta. Debido a este algunos autores han sugerido a Mayoría-p conocida alternativa del .
de PP contra el BPP
el BPP es un subconjunto del PP ; puede ser visto como el subconjunto para el cual hay algoritmos de probabilidad eficientes. La distinción está en la probabilidad de error se permite que: en el BPP, un algoritmo debe dar respuesta correcta (SÍ o NO) con la probabilidad que excede un cierto constante fijo c mayor el de 1/2, tal como 2/3 o 501/1000. Si éste es el caso, después podemos funcionar con el algoritmo un número constante de épocas y tomar mayoría de votos para alcanzar cualquier probabilidad deseada de la corrección menos de 1, usar el Chernoff encuadernado. Este número de repeticiones aumenta si el c se convierte más cercano al 1/2, pero no depende del n . La cosa importante es que este constante c no está permitido depender de la entrada. Por una parte, un algoritmo de los PP se permite para hacer algo como el siguiente:
En un caso del SÍ, salida SÍ con la probabilidad 1/2+1/2n, donde está la longitud el n de la entrada.
En un caso de NO, salida SÍ con la probabilidad el 1/2.
Porque son estas dos probabilidades así que cercano junto, especialmente para el grande n, incluso si lo funcionamos una gran cantidad de veces es muy difícil decir si estamos funcionando en un caso del SÍ o un caso de NO. El intentar alcanzar un nivel deseado fijo de la probabilidad usar mayoría de votos y el límite de Chernoff requiere un número de repeticiones que es exponencial en el n . Esto se puede comparar áspero al problema de intentar imaginar que el lado de una moneda leve-en polarización negativa es más probable moviéndola de un tirón muchas veces.
El PP comparó a otras clases de la complejidad
El PP contiene el BPP, puesto que los algoritmos de probabilidad descritos en la definición del BPP forman un subconjunto de ésos en la definición del PP .
El PP también contiene el NP . Para probar eso, demostramos que el problema NP-completo del satisfiability pertenece al PP . Considerar un algoritmo de probabilidad que, dado un F (x1, x2,…, xn) de la fórmula elija un x1, x2 de la asignación,…, xn uniformemente al azar. Entonces, el algoritmo comprueba si la asignación hace la fórmula F verdad. Si sí, hace salir SÍ. Si no, hace salir SÍ con la probabilidad el 1/2 y NO con la probabilidad el 1/2.
Si la fórmula es unsatisfiable, el algoritmo hará salir siempre SÍ con la probabilidad el 1/2. Si existe una asignación satisfying, hará salir SÍ con la probabilidad más el de 1/2 (exactamente el 1/2 si escogió una asignación y un 1 unsatisfying si escogió una asignación satisfying, haciendo un promedio a un cierto número mayor el de 1/2). Así, este algoritmo pone satisfiability en el PP . Pues el SAT es NP-completo, y podemos prefijar cualquier Polinómico-tiempo determinista mucho-uno la reducción sobre el algoritmo de los PP, el NP se contiene en el PP . Porque el PP es cerrado bajo complemento, también contiene el co- NP .
El PP también contiene el BQP, la clase del de problemas de decisión solubles por las computadoras polinómicas eficientes de Quantum del tiempo de hecho, BQP es el bajo para el PP, significando que una máquina de los PP no alcanza ninguna ventaja de poder solucionar problemas del BQP inmediatamente.
Una máquina polinómica de Turing del tiempo con un oráculo ( PPP ) de los PP puede solucionar todos los problemas en el pH, la jerarquía polinómica del entero. Este resultado fue demostrado por Seinosuke Toda en 1989 y se conoce como teorema de Toda. Ésta es evidencia de cómo es difícilmente solucionar problemas en el PP . El #P de la clase está en un cierto sentido alrededor como difícilmente, puesto que el #P del del P = el PPP y por lo tanto el #P del del del P contiene el pH también. El PP contiene terminantemente el TC0, la clase del de constante-profundidad, ilimitado-ventilador-en los circuitos boleanos con las puertas (Allender 1996 de la mayoría, según lo citado en Burtschick 1999). El PP se contiene en el PSPACE . Esto puede ser demostrada fácilmente exhibiendo un algoritmo del polinómico-espacio para el MAJSAT, definido abajo; intentar simplemente todas las asignaciones y contar el número los satisfacciones. Desemejante del BPP, PP está un sintáctico, algo que clase semántica. Cualquier máquina de probabilidad del polinómico-tiempo reconoce una cierta lengua en el PP . En cambio, dado una descripción de una máquina de probabilidad del polinómico-tiempo, es undecidable en general determinar si reconoce una lengua en el BPP . El PP tiene problemas completos naturales, por ejemplo, MAJSAT . El MAJSAT es un problema de decisión en cuál se da una fórmula boleana F. La respuesta debe ser SÍ si más que mitad de todo el x1, x2 de las asignaciones,…, xn hacen F verdad y NINGUÌN de otra manera. El PP es cerrado bajo el complemento y diferencia simétrica, y también bajo la unión e intersección . La prueba de los 3ultimos dos encierros es más difícil que los dos anteriores, y era un problema abierto por 14 años.
Terminar los problemas y otras características
Random links: Universidad de Ying Wa | La la Argentina | Chishu Ryu | División de Greenway | Jane Barton