PP (complejidad)

Clase de problemas en informática

PP en relación con otras clases de complejidad probabilística ( ZPP , RP , co-RP, BPP , BQP ), que generalizan P dentro de PSPACE . Se desconoce si alguna de estas inclusiones es estricta.

En teoría de la complejidad , PP o PPT es la clase de problemas de decisión que se pueden resolver mediante una máquina de Turing probabilística en tiempo polinomial , con una probabilidad de error de menos de 1/2 para todas las instancias. La abreviatura PP se refiere a 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 hay un algoritmo para él que puede lanzar monedas y tomar decisiones aleatorias. Se garantiza que se ejecutará en tiempo polinomial. Si la respuesta es SÍ, el algoritmo responderá SÍ con una probabilidad mayor que 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 pueden resolver con cualquier grado fijo de precisión ejecutando un algoritmo aleatorio de tiempo polinomial una cantidad suficiente (pero acotada) de veces.

Las máquinas de Turing que están limitadas polinómicamente y son probabilísticas se caracterizan como PPT , que significa máquinas de tiempo polinomial probabilísticas. ^[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 se pueden resolver con una máquina PPT con una probabilidad de error de menos de 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 una mayoría (más de la mitad) de caminos computacionales acepten. Debido a esto algunos autores han sugerido el nombre alternativo Majority-P . ^[3]

Definición

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

• M se ejecuta durante un tiempo polinomial en todas las entradas
• Para todo x en L , M da como resultado 1 con una probabilidad estrictamente mayor que 1/2
• Para todo x no en L , M da como resultado 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 durante un 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 es mayor que 1/2
• Para todo x no en L , la fracción de cadenas y de longitud p (| x |) que satisfacen M(x,y) = 1 es menor que 1/2.

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.

PP contra BPP

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 que se permite: en BPP , un algoritmo debe dar una 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, entonces podemos ejecutar el algoritmo varias veces y tomar una mayoría de votos para lograr cualquier probabilidad deseada de corrección 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 .

En términos más generales, si c puede depender del tamaño de entrada de forma polinómica, como , entonces podemos volver a ejecutar el algoritmo para y tomar la mayoría de votos. Por la desigualdad de Hoeffding , esto nos da un algoritmo BPP . ${\displaystyle n}$ ${\displaystyle c=O(n^{-k})}$ ${\displaystyle O(n^{2k})}$

Lo importante es que no se permite que esta constante c dependa de la entrada. Por otro lado, se permite que un algoritmo PP haga algo como lo siguiente:

• En una instancia de YES, genera YES con una probabilidad de 1/2 + 1/2 ⁿ , donde n es la longitud de la entrada.
• En una instancia NO, salida SÍ con probabilidad 1/2 − 1/2 ⁿ .

Debido a que estas dos probabilidades están exponencialmente próximas entre sí, incluso si lo ejecutamos una cantidad polinómica de veces, es muy difícil determinar si estamos operando en una instancia SÍ o en una instancia NO. Intentar lograr un nivel de probabilidad deseado fijo utilizando una mayoría de votos y el límite de Chernoff requiere una cantidad de repeticiones que es exponencial en n .

PP comparado 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 aquellos en la definición de PP .

PP también incluye NP . Para probar esto, mostramos que el problema de satisfacibilidad NP-completo pertenece a PP . Considere un algoritmo probabilístico que, dada una fórmula F ( x ₁ ,  x ₂ , ...,  x _n ) elige una asignación x ₁ ,  x ₂ , ...,  x _n uniformemente al azar. Luego, el algoritmo verifica si la asignación hace que la fórmula F sea verdadera. Si es así, genera SÍ. De lo contrario, genera SÍ con probabilidad y NO con probabilidad . ${\displaystyle {\frac {1}{2}}-{\frac {1}{2^{n+1}}}}$ ${\displaystyle {\frac {1}{2}}+{\frac {1}{2^{n+1}}}}$

Si la fórmula no es satisfacible, el algoritmo siempre dará como resultado SÍ con probabilidad . Si existe una asignación satisfactoria, dará como resultado SÍ con probabilidad al menos (exactamente 1/2 si eligió una asignación no satisfactoria y 1 si eligió una asignación satisfactoria, promediando a algún número mayor que 1/2). Por lo 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 es cerrado bajo complemento, también incluye co-NP . ${\displaystyle {\frac {1}{2}}-{\frac {1}{2^{n+1}}}<{\frac {1}{2}}}$ ${\displaystyle \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}}}$

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 de 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 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 ( P ^PP ) puede resolver todos los problemas en PH , la jerarquía polinomial completa . Este resultado fue demostrado por Seinosuke Toda en 1989 y se conoce como el teorema de Toda . Esto es evidencia de lo difícil que es resolver problemas en PP . La clase #P es en cierto sentido tan difícil, ya que P ^#P = P ^PP y por lo tanto P ^#P incluye PH también. ^[6]

PP incluye estrictamente TC 0 uniforme, la clase de circuitos booleanos de profundidad constante y abanico de entrada ilimitado 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 mostrando un algoritmo de espacio polinomial para MAJSAT , definido a continuación; simplemente pruebe todas las asignaciones y cuente la cantidad de las que cumplen con los requisitos.

PP no está incluido en TAMAÑO (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 idioma en PP . Por el contrario, dada una descripción de una máquina probabilística de tiempo polinomial, es indecidible en general determinar si reconoce un idioma 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 está cerrado bajo complemento

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

${\displaystyle x\in L\Rightarrow \Pr[A{\text{ accepts }}x]>{\frac {1}{2}}\quad {\text{and}}\quad x\not \in L\Rightarrow \Pr[A{\text{ accepts }}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 la máquina que es la misma que A excepto que acepta cuando A rechazaría, y viceversa. Entonces ${\displaystyle A^{c}}$ ${\displaystyle A^{c}}$

${\displaystyle 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 que implica que está en PP . ${\displaystyle L^{c}}$

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

${\displaystyle 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 ′ lanza monedas y rechaza si todas son caras y acepta en caso contrario. Entonces ${\displaystyle f(|x|)+1}$

${\displaystyle 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

${\displaystyle 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 prueba.

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

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 la poseselección , se obtiene una clase más grande llamada PostBQP . Informalmente, la poseselección le da al computador el siguiente poder: siempre que algún evento (como medir un qubit en un cierto estado) tenga probabilidad distinta de cero, se le permite asumir que ocurre. ^[11] Scott Aaronson demostró en 2004 que PostBQP es igual a PP . ^{[5] [12]} Esta reformulación de PP facilita 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 .

PQP

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 puede resolver una computadora cuántica en tiempo polinomial, con una probabilidad de error de menos de 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 sigue coincidiendo con PP . ^[13]

Notas

1. Gill, John (1977). "Complejidad computacional de máquinas de Turing probabilísticas". Revista SIAM de informática . 6 (4): 675–695. doi :10.1137/0206049.
2. Lindell, Yehuda; Katz, Jonathan (2015). Introducción a la criptografía moderna (2.ª edición). Chapman y Hall/CRC. pág. 46. ISBN 978-1-4665-7027-6.
3. Lance Fortnow. Computational Complexity: 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"
5. 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 . Código Bibliográfico :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". Revista SIAM de Computación . 20 (5): 865–877. doi :10.1137/0220053. MR  1115655.
7. Allender 1996, citado en Burtschick 1999
8. David Russo (1985). Propiedades estructurales de clases de complejidad (tesis doctoral). Universidad de California, Santa Bárbara.
9. R. Beigel, N. Reingold y DA Spielman, "PP está 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 posselección" . Consultado el 27 de julio de 2009 .
12. Aaronson, Scott (11 de enero de 2004). "Clase de complejidad de la semana: PP". Weblog sobre complejidad computacional . Consultado 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 . Código Bibliográfico : 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 Informática y Combinatoria (COCOON) . Apuntes de conferencias sobre informática. Vol. 1090. Springer-Verlag. págs. 127–135..
• Burtschick, Hans-Jörg; Vollmer, Heribert (1998). "Cuantificadores de Lindström y definibilidad del lenguaje de hojas". Int. J. Found. Comput. Sci . 9 (3): 277–294. doi :10.1142/S0129054198000180. ECCC  TR96-005.

Enlaces externos

• Zoológico de la complejidad : PP