En teoría de la complejidad , PP es la clase de problemas de decisión que pueden resolverse mediante una máquina probabilística de Turing en tiempo polinómico , con una probabilidad de error inferior a 1/2 para todos los casos. La abreviatura PP se refiere al tiempo polinomial probabilístico. La clase de complejidad fue definida por Gill en 1977. [1]
Si un problema de decisión está en PP , entonces existe un algoritmo que puede lanzar monedas y tomar decisiones aleatorias. Se garantiza que se ejecutará en tiempo polinómico. Si la respuesta es SÍ, el algoritmo responderá SÍ con una probabilidad superior a 1/2. Si la respuesta es NO, el algoritmo responderá SÍ con una probabilidad menor que 1/2. En términos más prácticos, es la clase de problemas que se puede resolver con cualquier grado fijo de precisión ejecutando un algoritmo aleatorio de tiempo polinomial un número suficiente (pero limitado) de veces.
Las máquinas de Turing que están ligadas polinómicamente y son probabilísticas se caracterizan como PPT , que significa máquinas probabilísticas de tiempo polinomial. [2] Esta caracterización de las máquinas de Turing no requiere una probabilidad de error limitada. Por lo tanto, PP es la clase de complejidad que contiene todos los problemas que puede resolver una máquina PPT con una probabilidad de error inferior a 1/2.
Una caracterización alternativa de PP es el conjunto de problemas que pueden resolverse mediante una máquina de Turing no determinista en tiempo polinómico donde la condición de aceptación es que la mayoría (más de la mitad) de las rutas de cálculo acepten. Debido a esto, algunos autores han sugerido el nombre alternativo Majority-P . [3]
Un lenguaje L está en PP si y sólo si existe una máquina de Turing probabilística M , tal que
Alternativamente, PP se puede definir utilizando únicamente máquinas de Turing deterministas. Un lenguaje L está en PP si y sólo si existe un polinomio p y una máquina de Turing determinista M , tal que
En ambas definiciones, "menor que" se puede cambiar a "menor o igual que" (ver más abajo), y el umbral 1/2 se puede reemplazar por cualquier número racional fijo en (0,1), sin cambiar la clase.
BPP es un subconjunto de PP ; puede verse como el subconjunto para el cual existen algoritmos probabilísticos eficientes. La distinción está en la probabilidad de error permitida: en BPP , un algoritmo debe dar una respuesta correcta (SÍ o NO) con una probabilidad que exceda alguna constante fija c > 1/2, como 2/3 o 501/1000. Si este es el caso, entonces podemos ejecutar el algoritmo varias veces y obtener una votación mayoritaria para lograr cualquier probabilidad de corrección deseada menor que 1, utilizando el límite de Chernoff . Este número de repeticiones aumenta si c se acerca a 1/2, pero no depende del tamaño de entrada n .
De manera más general, si c puede depender polinómicamente del tamaño de entrada , como , entonces podemos volver a ejecutar el algoritmo y obtener el voto mayoritario. Por la desigualdad de Hoeffding , esto nos da un algoritmo BPP .
Lo importante es que no se permite que esta constante c dependa de la entrada. Por otro lado, a un algoritmo PP se le permite hacer algo como lo siguiente:
Debido a que estas dos probabilidades están exponencialmente juntas, incluso si lo ejecutamos un número polinómico de veces, es muy difícil saber si estamos operando en una instancia SÍ o en una instancia NO. Intentar alcanzar un nivel de probabilidad fijo deseado utilizando una mayoría de votos y el límite de Chernoff requiere un número de repeticiones que es exponencial en n .
PP incluye BPP , ya que los algoritmos probabilísticos descritos en la definición de BPP forman un subconjunto de los de la definición de PP .
El PP también incluye al NP . Para probar esto, demostramos que el problema de satisfacibilidad completa NP pertenece al PP . Considere un algoritmo probabilístico que, dada una fórmula F ( x 1 , x 2 , ..., x n ) elige una asignación x 1 , x 2 , ..., x n uniformemente al azar. Luego, el algoritmo verifica si la asignación hace que la fórmula F sea verdadera. En caso afirmativo, genera SÍ. De lo contrario, genera SÍ con probabilidad y NO con probabilidad .
Si la fórmula no es satisfactoria, el algoritmo siempre generará SÍ con probabilidad . Si existe una tarea satisfactoria, generará SÍ con probabilidad al menos (exactamente 1/2 si eligió una tarea insatisfactoria y 1 si eligió una tarea satisfactoria, con un promedio de algún número mayor que 1/2). Por tanto, este algoritmo pone la satisfacibilidad en PP . Como SAT es NP-completo, y podemos anteponer cualquier reducción determinista de muchos-uno en tiempo polinomial al algoritmo PP , NP se incluye en PP . Debido a que PP está cerrado bajo complemento, también incluye co-NP .
Además, PP incluye MA , [4] que subsume las dos inclusiones anteriores.
PP también incluye BQP , la clase de problemas de decisión que pueden resolverse mediante computadoras cuánticas de tiempo polinomial eficientes . De hecho, BQP es bajo para PP , lo que significa que una máquina PP no obtiene ningún beneficio al poder resolver problemas de BQP al instante. La clase de tiempo polinomial en computadoras cuánticas con poselección , PostBQP , es igual a PP [5] (ver #PostBQP a continuación).
Además, PP incluye QMA , que incluye inclusiones de MA y BQP .
Una máquina de Turing de tiempo polinomial con un oráculo PP ( PP PP ) puede resolver todos los problemas en PH , toda la jerarquía polinómica . Este resultado fue demostrado por Seinosuke Toda en 1989 y se conoce como teorema de Toda . Esto es una prueba de lo difícil que es resolver los problemas en el PP . La clase #P es en cierto sentido igual de difícil, ya que P #P = P PP y por lo tanto P #P incluye también PH . [6]
PP incluye estrictamente el TC 0 uniforme, la clase de circuitos booleanos de entrada ilimitada y de profundidad constante con puertas mayoritarias que son uniformes (generadas por un algoritmo de tiempo polinomial). [7]
PP está incluido en PSPACE . Esto se puede demostrar fácilmente exhibiendo un algoritmo de espacio polinomial para MAJSAT , definido a continuación; simplemente prueba todas las tareas y cuenta el número de las que te satisfagan.
PP no está incluido en TAMAÑO (n k ) para cualquier k, según el teorema de Kannan .
A diferencia de BPP , PP es una clase sintáctica más que semántica. Cualquier máquina probabilística de tiempo polinomial reconoce algún lenguaje en PP . Por el contrario, dada una descripción de una máquina probabilística de tiempo polinomial, en general es indecidible determinar si reconoce un lenguaje en BPP .
PP tiene problemas completos naturales, por ejemplo, MAJSAT . [1] MAJSAT es un problema de decisión en el que se le da una fórmula booleana F. La respuesta debe ser SÍ si más de la mitad de todas las asignaciones x 1 , x 2 , ..., x n hacen que F sea verdadera y NO en caso contrario.
Sea L un lenguaje en PP . Denotemos el complemento de L . Según la definición de PP existe un algoritmo probabilístico A de tiempo polinomial con la propiedad de que
Afirmamos que, sin pérdida de generalidad , esta última desigualdad es siempre estricta; El teorema se puede deducir de esta afirmación: denotemos la máquina que es igual a A excepto que acepta cuando A rechaza, y viceversa. Entonces
lo que implica que está en PP .
Ahora justificamos nuestro supuesto sin pérdida de generalidad. Sea el límite superior del polinomio en el tiempo de ejecución de A en la entrada x . Por lo tanto, A realiza como máximo lanzamientos de moneda aleatorios durante su ejecución. En particular la probabilidad de aceptación es un múltiplo entero de y tenemos:
Defina una máquina A ′ de la siguiente manera: en la entrada x , A ′ ejecuta A como una subrutina y rechaza si A rechazaría; de lo contrario, si A aceptara, A ′ lanza monedas y las rechaza si todas son caras, y acepta en caso contrario. Entonces
Esto justifica la suposición (ya que A ′ sigue siendo un algoritmo probabilístico de tiempo polinómico) y completa la prueba.
David Russo demostró en su doctorado de 1985. tesis [8] de que PP está cerrado bajo diferencia simétrica . Fue un problema abierto durante 14 años si el PP se cerraba bajo unión e intersección ; Esto fue resuelto afirmativamente por Beigel, Reingold y Spielman. [9] Posteriormente, Li [10] y Aaronson proporcionaron pruebas alternativas (ver #PostBQP a continuación).
La clase de complejidad cuántica BQP es la clase de problemas que se pueden resolver en tiempo polinomial en una máquina cuántica de Turing . Al agregar postselección se obtiene una clase más grande llamada PostBQP . De manera informal, la poselección le da a la computadora el siguiente poder: siempre que algún evento (como medir un qubit en un estado determinado) tenga una probabilidad distinta de cero, se le permite asumir que tiene lugar. [11] Scott Aaronson demostró en 2004 que PostBQP es igual a PP . [5] [12] Esta reformulación de PP hace que sea más fácil mostrar ciertos resultados, como que PP está cerrado bajo intersección (y por lo tanto, bajo unión), que BQP es bajo para PP y que QMA está incluido en PP .
PP también es igual a otra clase de complejidad cuántica conocida como PQP , que es el análogo de error ilimitado de BQP . Denota la clase de problemas de decisión que una computadora cuántica puede resolver en tiempo polinómico, con una probabilidad de error menor que 1/2 para todos los casos. Incluso si todas las amplitudes utilizadas para el cálculo de PQP se extraen de números algebraicos, PQP coincide con PP . [13]
![{\displaystyle x\in L\Rightarrow \Pr[A{\text{ acepta }}x]>{\frac {1}{2}}\quad {\text{y}}\quad x\not \in L \Rightarrow \Pr[A{\text{ acepta }}x]\leq {\frac {1}{2}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36b7d0af544a09f395d54f66525405920f90ccee)
![{\displaystyle x\in L^{c}\Rightarrow \Pr[A^{c}{\text{ acepta }}x]>{\frac {1}{2}}\quad {\text{y}} \quad x\not \in L^{c}\Rightarrow \Pr[A^{c}{\text{ acepta }}x]<{\frac {1}{2}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cec7b6d455f638f43467005bd5e3778308f0fc70)
![{\displaystyle x\in L\Rightarrow \Pr[A{\text{ acepta }}x]\geq {\frac {1}{2}}+{\frac {1}{2^{f(|x| )}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e6815df0098debe032c48d27f96993f8d8a5bf9)
![{\displaystyle x\not \in L\Rightarrow \Pr[A'{\text{ acepta }}x]\leq {\frac {1}{2}}\cdot \left(1-{\frac {1} {2^{f(|x|)+1}}}\right)<{\frac {1}{2}}\quad {\text{y}}\quad x\in L\Rightarrow \Pr[A '{\text{ acepta }}x]\geq \left({\frac {1}{2}}+{\frac {1}{2^{f(|x|)}}}\right)\cdot \left(1-{\frac {1}{2^{f(|x|)+1}}}\right)>{\frac {1}{2}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/746f10a295fb2e4e5e2e7ca2c9b4c349308cacc3)