PP (complejidad)

En teoría de la complejidad , PP , o PPT, es la clase de problemas de decisión que puede resolver una máquina de Turing probabilística en tiempo polinomial , con una probabilidad de error menor que 1/2 para todas las instancias. La abreviatura PP se refiere a tiempo polinomial probabilístico. Esta clase de complejidad fue definida por Gill en 1977. ^{[ 1 ]}

Si un problema de decisión pertenece a PP , entonces existe un algoritmo que se ejecuta en tiempo polinomial y que puede tomar decisiones aleatorias, de modo que devuelve la respuesta correcta con una probabilidad superior a 1/2. En términos más prácticos, se trata de la clase de problemas que pueden resolverse 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 con complejidad polinomial y probabilísticas se caracterizan como PPT , siglas de máquinas de tiempo polinomial probabilísticas. ^{[ 2 ]} Esta caracterización de las máquinas de Turing no requiere una probabilidad de error acotada. Por lo tanto, PP es la clase de complejidad que contiene todos los problemas resolubles por una máquina PPT con una probabilidad de error menor que 1/2.

Una caracterización alternativa de PP es el conjunto de problemas que pueden ser resueltos por una máquina de Turing no determinista en tiempo polinomial, donde la condición de aceptación es que la mayoría (más de la mitad) de las rutas de cálculo sean aceptadas. Debido a esto, algunos autores han sugerido el nombre alternativo Majority-P . ^{[ 3 ]}

Definición

Un lenguaje L está en PP si y solo si existe una máquina de Turing probabilística M tal que

M se ejecuta en tiempo polinomial en todas las entradas.
Para todo x en L , M produce 1 con una probabilidad no menor que 1/2.
Para todo x que no esté en L , M produce 1 con una probabilidad estrictamente menor que 1/2.

Alternativamente, PP puede definirse utilizando únicamente máquinas de Turing deterministas. Un lenguaje L está en PP si y solo si existe un polinomio p y una máquina de Turing determinista M tales que

M se ejecuta en tiempo polinomial en todas las entradas.
Para todo x en L , la fracción de cadenas y de longitud p (| x |) que satisfacen M ( x , y ) = 1 no es menor que 1/2
Para todo x que no está en L , la fracción de cadenas y de longitud p (| x |) que satisfacen M ( x , y ) = 1 es menor que 1/2.

En esta definición, la cadena " y" corresponde al resultado de los lanzamientos aleatorios de moneda que habría realizado la máquina de Turing probabilística.

En ambas definiciones, "menor que" se puede cambiar por "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.

PP frente a BPP

BPP es un subconjunto de PP ; puede considerarse como el subconjunto para el cual existen algoritmos probabilísticos eficientes. La distinción radica en la probabilidad de error permitida: en BPP , un algoritmo debe dar la respuesta correcta (SÍ o NO) con una probabilidad que exceda una constante fija c > 1/2, como 2/3 o 501/1000. Si este es el caso, podemos ejecutar el algoritmo varias veces y tomar una votación mayoritaria para lograr cualquier probabilidad de corrección deseada menor que 1, utilizando la cota de Chernoff . Este número de repeticiones aumenta si c se acerca a 1/2, pero no depende del tamaño de la entrada n .

De forma más general, si c puede depender del tamaño de la entrada. $n$ polinómicamente, como $c=O(n^{-k})$ , entonces podemos volver a ejecutar el algoritmo para $O(n^{2k})$ y tomar la votación mayoritaria. Por la desigualdad de Hoeffding , esto nos da un algoritmo BPP .

Lo importante es que esta constante c no puede depender de la entrada. Por otro lado, un algoritmo PP puede hacer algo como lo siguiente:

En caso de que sea SÍ, la salida es SÍ con una probabilidad de 1/2 + 1/2 ⁿ , donde n es la longitud de la entrada.
En caso de NO, la salida es SÍ con una probabilidad de 1/2 − 1/2 ⁿ .

Debido a que estas dos probabilidades están exponencialmente cerca, incluso si lo ejecutamos un número polinomial de veces, es muy difícil determinar si estamos operando sobre un caso de SÍ o un caso de NO. Intentar alcanzar un nivel de probabilidad deseado fijo utilizando una votación mayoritaria y la cota de Chernoff requiere un número de repeticiones que es exponencial en n .

PP en comparación con otras clases de complejidad

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 .

PP _también incluye NP . Para demostrarlo, mostramos que el problema _desatisfacibilidad NP-completo pertenece a PP . Consideremos un algoritmo probabilístico que, dada una fórmula F ( x₁ , x₂ , ..., xn ) _, elige una asignación x₁ _,x₂ , _... , xn uniformemente al azar. Luego, el algoritmo comprueba si la asignación hace que la fórmula F sea verdadera. Si _es así, imprime SÍ. De lo contrario, imprime SÍ con probabilidad ${\frac {1}{2}}-{\frac {1}{2^{n+1}}}$ y NO con probabilidad ${\frac {1}{2}}+{\frac {1}{2^{n+1}}}$ .

Si la fórmula no se puede satisfacer, el algoritmo siempre devolverá SÍ con probabilidad ${\frac {1}{2}}-{\frac {1}{2^{n+1}}}<{\frac {1}{2}}$ . Si existe una asignación satisfactoria, mostrará SÍ con una probabilidad de al menos $\left({\frac {1}{2}}-{\frac {1}{2^{n+1}}}\right)\cdot \left(1-{\frac {1}{2^{n}}}\right)+1\cdot {\frac {1}{2^{n}}}={\frac {1}{2}}+{\frac {1}{2^{2n+1}}}>{\frac {1}{2}}$ (exactamente 1/2 si escogió una asignación insatisfactoria y 1 si escogió una asignación satisfactoria, promediando a algún número mayor que 1/2). Por lo tanto, este algoritmo coloca la satisfacibilidad en PP . Como SAT es NP-completo, y podemos anteponer cualquier reducción determinista de muchos a uno de tiempo polinomial al algoritmo PP , NP está incluido en PP . Debido a que PP es cerrado bajo complemento, también incluye co-NP .

Además, PP incluye MA , ^{[ 4 ]} que engloba las dos inclusiones anteriores.

PP también incluye BQP , la clase de problemas de decisión que pueden resolverse mediante computadoras cuánticas eficientes de tiempo polinomial . De hecho, BQP es bajo para PP , lo que significa que una máquina PP no obtiene ningún beneficio al poder resolver problemas BQP instantáneamente. La clase de tiempo polinomial en computadoras cuánticas con postselección , PostBQP , es igual a PP ^{[ 5 ]} (ver #PostBQP más abajo).

Además, PP incluye QMA , que engloba las inclusiones de MA y BQP .

Una máquina de Turing de tiempo polinomial con un oráculo ^PP ( PPPP ) puede resolver todos los problemas en PH , toda la jerarquía polinomial . Este resultado fue demostrado por Seinosuke Toda en 1989 y se conoce como el teorema de Toda . Esto evidencia la dificultad de resolver problemas en PP . La clase #P es, en cierto sentido, igual de difícil, ya que P ^#P = PPPP y, por lo tanto, ^P # ^P también incluye PH . ^{[ 6 ]}

PP incluye estrictamente TC ⁰ uniforme, la clase de circuitos booleanos de profundidad constante y entrada de fan ilimitada con compuertas de mayoría que son uniformes (generados por un algoritmo de tiempo polinomial). ^{[ 7 ]}

PP está incluido en PSPACE . Esto se puede demostrar fácilmente mostrando un algoritmo de espacio polinomial para MAJSAT , definido a continuación; simplemente pruebe todas las asignaciones y cuente el número de las que satisfacen.

PP no está incluido en SIZE (n ^k ) para ningún k, según el teorema de Kannan .

Problemas completos y otras propiedades

A diferencia de BPP , PP es una clase sintáctica, no semántica. Cualquier máquina probabilística de tiempo polinomial reconoce algún lenguaje en PP . En cambio, 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 da una fórmula booleana F. La respuesta debe ser SÍ si más de la mitad de todas las asignaciones x ₁ , x ₂ , ..., x _n hacen que F sea verdadera y NO en caso contrario.

Prueba de que PP es cerrado bajo complemento

Sea L un lenguaje en PP . $L^{c}$ denotemos el complemento de L. Por la definición de PP existe un algoritmo probabilístico de tiempo polinomial A con la propiedad de que

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}}.

Afirmamos que, sin pérdida de generalidad , la última desigualdad es siempre estricta; el teorema se puede deducir de esta afirmación: sea $A^{c}$ denotamos la máquina que es igual a A excepto que $A^{c}$ acepta cuando A rechazaría, y viceversa. Entonces

x\in L^{c}\Rightarrow \Pr[A^{c}{\text{ accepts }}x]>{\frac {1}{2}}\quad {\text{and}}\quad x\not \in L^{c}\Rightarrow \Pr[A^{c}{\text{ accepts }}x]<{\frac {1}{2}},

lo cual implica que $L^{c}$ está en PP .

Ahora justificamos nuestra suposición sin pérdida de generalidad. $f(|x|)$ Sea el límite superior polinómico del tiempo de ejecución de A en la entrada x . Por lo tanto, A realiza como máximo $f(|x|)$ lanzamientos de moneda aleatorios durante su ejecución. En particular, la probabilidad de aceptación es un múltiplo entero de $2^{-f(|x|)}$ y tenemos:

x\in L\Rightarrow \Pr[A{\text{ accepts }}x]\geq {\frac {1}{2}}+{\frac {1}{2^{f(|x|)}}}.

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 aceptaría, A ′ cambia de estado. $f(|x|)+1$ Monedas y rechaza si todas son caras, y acepta en caso contrario.

x\not \in L\Rightarrow \Pr[A'{\text{ accepts }}x]\leq {\frac {1}{2}}\cdot \left(1-{\frac {1}{2^{f(|x|)+1}}}\right)<{\frac {1}{2}}

y

x\in L\Rightarrow \Pr[A'{\text{ accepts }}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}}.

Esto justifica la suposición (ya que A ′ sigue siendo un algoritmo probabilístico de tiempo polinomial) y completa la demostración.

David Russo demostró en su tesis doctoral de 1985 ^{[ 8 ]} que PP es cerrado bajo la diferencia simétrica . Durante 14 años fue un problema abierto si PP era cerrado bajo la unión y la intersección ; Beigel, Reingold y Spielman lo resolvieron afirmativamente. ^{[ 9 ] Posteriormente, Li}^{[ 10 ]} y Aaronson dieron demostraciones alternativas (véase #PostBQP más abajo).

Otras clases de complejidad equivalentes

PostBQP

La clase de complejidad cuántica BQP es la clase de problemas resolubles en tiempo polinomial en una máquina de Turing cuántica . Al agregar postselección , se obtiene una clase más grande llamada PostBQP . De manera informal, la postselección le da a la computadora el siguiente poder: siempre que algún evento (como medir un cúbit en un estado determinado) tenga una probabilidad distinta de cero, se puede asumir que tiene lugar. ^{[ 11 ]} Scott Aaronson demostró en 2004 que PostBQP es igual a PP . ^{[ 5 ]}^{[ 12 ]} Esta reformulación de PP hace más fácil demostrar ciertos resultados, como que PP es cerrado bajo intersección (y por lo tanto, bajo unión), que BQP es bajo para PP , y que QMA está incluido en PP .

PQP

PP también es igual a otra clase de complejidad cuántica conocida como PQP , que es el análogo de error no acotado de BQP . Denota la clase de problemas de decisión que puede resolver una computadora cuántica en tiempo polinomial, con una probabilidad de error menor que 1/2 para todas las instancias. Incluso si todas las amplitudes utilizadas para el cálculo de PQP se extraen de números algebraicos, PQP sigue coincidiendo con PP . ^{[ 13 ]}

Notas

1 2 Gill, John (1977). "Complejidad computacional de las máquinas de Turing probabilísticas". SIAM Journal on Computing . 6 (4): 675– 695. doi : 10.1137/0206049 .
↑ Lindell, Yehuda; Katz, Jonathan (2015). Introducción a la criptografía moderna (2.ª ed.). Chapman and Hall/CRC. pág. 46. ISBN 978-1-4665-7027-6.
↑ Lance Fortnow. Complejidad Computacional: Miércoles, 4 de septiembre de 2002: Clase de Complejidad de la Semana: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html
↑ "NK Vereshchagin, "Sobre el poder del PP"" . Archivado del original el 29-12-2014 . Consultado el 17-08-2011 .
1 2 Aaronson, Scott (2005). "Computación cuántica, postselección y tiempo polinomial probabilístico". Actas de la Royal Society A. 461 ( 2063): 3473–3482 . arXiv : quant-ph/0412187 . Bibcode : 2005RSPSA.461.3473A . doi : 10.1098/rspa.2005.1546 . S2CID 1770389 .
↑ Toda, Seinosuke (1991). "PP es tan difícil como la jerarquía de tiempo polinomial". SIAM Journal on Computing . 20 (5): 865– 877. doi : 10.1137/0220053 . MR 1115655 .
↑ Allender 1996, citado en Burtschick 1999
↑ David Russo (1985). Propiedades estructurales de las clases de complejidad (Tesis doctoral). Universidad de California, Santa Bárbara.
↑ R. Beigel, N. Reingold y DA Spielman, " PP es cerrado bajo intersección ", Actas del Simposio ACM sobre Teoría de la Computación de 1991 , págs. 1–9, 1991.
↑ Lide Li (1993). Sobre las funciones de conteo (Tesis doctoral). Universidad de Chicago.
↑ Aaronson, Scott. "El asombroso poder de la postselección" . Recuperado el 27 de julio de 2009 .
↑ Aaronson, Scott (11 de enero de 2004). "Clase de complejidad de la semana: PP" . Blog de complejidad computacional . Recuperado el 2 de mayo de 2008 .
↑ Yamakami, Tomoyuki (1999). "Análisis de funciones cuánticas". Int. J. Found. Comput. Sci. 14 (5): 815– 852. arXiv : quant-ph/9909012 . Bibcode : 1999quant.ph..9012Y . doi : 10.1142/S0129054103002047 . S2CID 3265603 .

Referencias

Papadimitriou, C. (1994). "Capítulo 11". Complejidad computacional . Addison-Wesley..
Allender, E. (1996). "Una nota sobre límites inferiores de circuitos uniformes para la jerarquía de conteo". Actas de la 2.ª Conferencia Internacional de Computación y Combinatoria (COCOON) . Lecture Notes in Computer Science. Vol. 1090. Springer-Verlag. pp. 127–135 . .
Burtschick, Hans-Jörg; Vollmer, Heribert (1998). "Cuantificadores de Lindström y definibilidad del lenguaje hoja". Int. J. Found. Comput. Sci . 9 (3): 277– 294. doi : 10.1142/S0129054198000180 . ECCC TR96-005 .

Enlaces externos

Zoológico de la complejidad : PP

[gill-1] 1 2 Gill, John (1977). "Complejidad computacional de las máquinas de Turing probabilísticas". SIAM Journal on Computing . 6 (4): 675– 695. doi : 10.1137/0206049 .

[2] Lindell, Yehuda; Katz, Jonathan (2015). Introducción a la criptografía moderna (2.ª ed.). Chapman and Hall/CRC. pág. 46. ISBN 978-1-4665-7027-6.

[3] Lance Fortnow. Complejidad Computacional: Miércoles, 4 de septiembre de 2002: Clase de Complejidad de la Semana: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html

[4] "NK Vereshchagin, "Sobre el poder del PP"" . Archivado del original el 29-12-2014 . Consultado el 17-08-2011 .

[PostBQP_=_PP-5] 1 2 Aaronson, Scott (2005). "Computación cuántica, postselección y tiempo polinomial probabilístico". Actas de la Royal Society A. 461 ( 2063): 3473–3482 . arXiv : quant-ph/0412187 . Bibcode : 2005RSPSA.461.3473A . doi : 10.1098/rspa.2005.1546 . S2CID 1770389 .

[6] Toda, Seinosuke (1991). "PP es tan difícil como la jerarquía de tiempo polinomial". SIAM Journal on Computing . 20 (5): 865– 877. doi : 10.1137/0220053 . MR 1115655 .

[7] Allender 1996, citado en Burtschick 1999

[8] David Russo (1985). Propiedades estructurales de las clases de complejidad (Tesis doctoral). Universidad de California, Santa Bárbara.

[9] R. Beigel, N. Reingold y DA Spielman, " PP es cerrado bajo intersección ", Actas del Simposio ACM sobre Teoría de la Computación de 1991 , págs. 1–9, 1991.

[10] Lide Li (1993). Sobre las funciones de conteo (Tesis doctoral). Universidad de Chicago.

[11] Aaronson, Scott. "El asombroso poder de la postselección" . Recuperado el 27 de julio de 2009 .

[12] Aaronson, Scott (11 de enero de 2004). "Clase de complejidad de la semana: PP" . Blog de complejidad computacional . Recuperado el 2 de mayo de 2008 .

[13] Yamakami, Tomoyuki (1999). "Análisis de funciones cuánticas". Int. J. Found. Comput. Sci. 14 (5): 815– 852. arXiv : quant-ph/9909012 . Bibcode : 1999quant.ph..9012Y . doi : 10.1142/S0129054103002047 . S2CID 3265603 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ] Posteriormente, Li

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]