En la teoría de la complejidad , PP 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 de menos de 1/2 para todos los casos. La abreviatura PP se refiere al tiempo polinomial probabilístico. La clase de complejidad fue definida [1] por Gill en 1977.
Si un problema de decisión está en PP , entonces existe un algoritmo que permite lanzar monedas y tomar decisiones al azar. Se garantiza que se ejecuta en tiempo polinomial. Si la respuesta es SÍ, el algoritmo responderá SÍ con una probabilidad de más de 1/2. Si la respuesta es NO, el algoritmo responderá SÍ con probabilidad menor o igual a 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 de tiempo polinomial aleatorio un número suficiente (pero acotado) de veces.
Las máquinas de Turing que están unidas por polinomios 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 acotada. Por 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 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 aceptan. Debido a esto, algunos autores han sugerido el nombre alternativo Majority-P . [3]
Definición
Una lengua L está en PP si y sólo si existe una máquina de Turing probabilística M , tal que
- M se ejecuta por tiempo polinomial en todas las entradas
- Para todo x en L , M produce 1 con probabilidad estrictamente mayor que 1/2
- Para todo x que no esté en L , M produce 1 con probabilidad menor o igual a 1/2.
Alternativamente, PP se puede definir utilizando solo máquinas de Turing deterministas. Un lenguaje L está en PP si y solo si existe un polinomio py una máquina de Turing determinista M , tal que
- M se ejecuta por 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 estrictamente mayor 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 o igual a 1/2.
En ambas definiciones, "menor o igual" se puede cambiar a "menor 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 verse como el subconjunto para el que 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 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 .
Lo importante es que no se permite que esta constante c dependa de la entrada. Por otro lado, un algoritmo PP puede hacer algo como lo siguiente:
- En una instancia YES, emita YES con probabilidad 1/2 + 1/2 n , donde n es la longitud de la entrada.
- En una instancia NO, emita SÍ con probabilidad 1/2 - 1/2 n .
Debido a que estas dos probabilidades están muy próximas, especialmente para n grandes , incluso si lo ejecutamos una gran cantidad de veces, es muy difícil saber si estamos operando en una instancia YES o una instancia NO. Intentar alcanzar un nivel de probabilidad fijo deseado usando un voto mayoritario y el límite de Chernoff requiere un número de repeticiones que es exponencial en n .
PP en comparación con otras clases de complejidad
PP contiene 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 contiene NP . Para probar esto, mostramos que el problema de satisfacebilidad NP-completo pertenece a 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. Si es así, da como resultado SÍ. De lo contrario, emite SÍ con probabilidad y NO con probabilidad .
Si la fórmula no es satisfactoria, el algoritmo siempre dará como resultado SÍ con probabilidad . Si existe una asignación satisfactoria, dará como resultado SÍ con una probabilidad de al menos(exactamente 1/2 si eligió una tarea insatisfactoria y 1 si eligió una tarea satisfactoria, con un promedio de un número mayor que 1/2). Por tanto, este algoritmo pone satisfacibilidad en PP . Como SAT es NP-completo, y podemos prefijar cualquier reducción determinista de tiempo polinomial muchos-uno en el algoritmo PP , NP está contenido en PP . Debido a que PP está cerrado bajo complemento, también contiene co-NP .
Además, PP contiene MA , [4] que subsume las dos inclusiones anteriores.
PP también contiene BQP , la clase de problemas de decisión que pueden resolverse mediante eficientes computadoras cuánticas de tiempo polinomial . De hecho, BQP es bajo para PP , lo que significa que una máquina de PP no logra ningún beneficio al poder resolver los problemas de BQP al instante. La clase de tiempo polinomial en computadoras cuánticas con posselección , PostBQP , es igual a PP [5] (ver #PostBQP más abajo).
Además, PP contiene QMA , que incluye inclusiones de MA y BQP .
A tiempo polinómico máquina de Turing con un PP Oracle ( P PP ) puede resolver todos los problemas en PH , toda la jerarquía polinomio . Este resultado fue mostrado por Seinosuke Toda en 1989 y se conoce como teorema de Toda . Esta es una prueba 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 también contiene PH .
PP contiene estrictamente TC 0 , la clase de circuitos booleanos uniformes de entrada de ventilador ilimitado y profundidad constante con compuertas mayoritarias . (Allender 1996, citado en Burtschick 1999).
PP está contenido en PSPACE . Esto se puede demostrar fácilmente mostrando un algoritmo de espacio polinómico para MAJSAT , definido a continuación; simplemente intente todas las tareas y cuente el número de satisfactorias.
PP no está contenido en SIZE (n k ) para ningún k ( prueba ).
Problemas completos y otras propiedades
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 . En contraste, dada una descripción de una máquina probabilística de tiempo polinomial, es indecidible en general determinar si reconoce un lenguaje en BPP .
PP tiene problemas naturales completos, por ejemplo, MAJSAT . 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.
Prueba de que PP está cerrado bajo complemento
Sea L un idioma en PP . Dejardenotan el complemento de L . Según la definición de PP, existe un algoritmo probabilístico de tiempo polinómico A 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: seadenotar la máquina que es la misma que A excepto queacepta cuando A rechazaría, y viceversa. Luego
lo que implica que está en PP .
Ahora justificamos nuestro supuesto sin pérdida de generalidad. Dejarser el límite superior del polinomio en el tiempo de ejecución de A en la entrada x . Así, A hace como máximomoneda al azar se lanza 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 rechazara; de lo contrario, si A aceptaría, A ′ volteamonedas y rechaza si todas son caras, y acepta lo contrario. Luego
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 Ph.D. de 1985. tesis [6] de que PP se cierra bajo diferencia simétrica . Fue un problema abierto durante 14 años si el PP se cerró bajo unión e intersección ; esto fue resuelto afirmativamente por Beigel, Reingold y Spielman. [7] Más tarde, Li [8] y Aaronson dieron demostraciones alternativas (ver #PostBQP a continuación).
Otras clases de complejidad equivalentes
PostBQP
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 postselección le da a la computadora el siguiente poder: siempre que algún evento (como medir un qubit en un cierto estado) tiene una probabilidad distinta de cero, se le permite asumir que tiene lugar. [9] Scott Aaronson demostró en 2004 que PostBQP es igual a PP . [5] [10] Esta reformulación de PP facilita mostrar ciertos resultados, como que PP está cerrado bajo intersección (y por tanto, bajo unión), que BQP es bajo para PP y que QMA está contenido 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 coincide con PP . [11]
Notas
- ^ Gill, John (1977). "Complejidad computacional de las máquinas probabilísticas de Turing". Revista SIAM de Computación . 6 (4): 675–695. doi : 10.1137 / 0206049 .
- ^ Lindell, Yehuda; Katz, Jonathan (2015). Introducción a la criptografía moderna (2 ed.). Chapman y Hall / CRC. pag. 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"
- ^ a b Aaronson, Scott (2005). "Computación cuántica, postselección y polinomio probabilístico-tiempo". Proceedings of the Royal Society A . 461 (2063): 3473–3482. arXiv : quant-ph / 0412187 . Código bibliográfico : 2005RSPSA.461.3473A . doi : 10.1098 / rspa.2005.1546 .
- ^ 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 is closed under intersection ", Actas del Simposio ACM sobre Teoría de la Computación 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" . Consultado el 27 de julio de 2009 .
- ^ Aaronson, Scott (11 de enero de 2004). "Clase de complejidad de la semana: PP" . Weblog de complejidad computacional . Consultado el 2 de mayo de 2008 .
- ^ Yamakami, Tomoyuki (1999). "Análisis de funciones cuánticas". En t. J. Encontrado. Computación. Sci . 14 (5): 815–852. arXiv : quant-ph / 9909012 . Código bibliográfico : 1999quant.ph..9012Y .
Referencias
- Papadimitriou, C. (1994). "Capítulo 11". Complejidad computacional . Addison-Wesley..
- Allender, E. (1996). "Una nota sobre los límites inferiores del circuito uniforme para la jerarquía de conteo". Actas II Congreso Internacional de Computación y Combinatoria (COCOON) . Apuntes de conferencias en Ciencias de la Computación. 1090 . Springer-Verlag. págs. 127-135..
- Burtschick, Hans-Jörg; Vollmer, Heribert (1999). "Cuantificadores de Lindström y definibilidad del lenguaje hoja". ECCC TR96-005 . Cite journal requiere
|journal=
( ayuda ).
enlaces externos
- Complejidad Zoo : PP