P/poly

En la teoría de la complejidad computacional, P/poly es la clase de complejidad de los lenguajes reconocidos por una máquina de Turing de tiempo polinomial con una función de asesoramiento limitada polinomialmente. También se define de manera equivalente como la clase PSIZE de lenguajes que tienen circuitos de tamaño polinómico.^[1]^[2] Esto significa que la máquina que reconoce un idioma puede usar una función de asesoramiento diferente o un circuito diferente dependiendo de la longitud de la entrada y que la función o circuito de asesoramiento variará solo según el tamaño de la entrada.

Por ejemplo, la popular prueba de primalidad Miller-Rabin puede formularse como un algoritmo P/poly: el "consejo" es una lista de candidatos a valores para probar. Es posible calcular previamente una lista de, como máximo, n valores de modo que cada número compuesto de n bits se asegure de tener un testigo a en la lista. Por ejemplo, para determinar correctamente la primalidad de los números de 32 bits, es suficiente probar a = 2, 7 y 61.^[3] La existencia de listas cortas de testigos candidatos sigue del hecho de que para cada n compuesto, 3/4s de todos los valores posibles son testigos; un simple argumento de recuento similar a la de la prueba de que BPP en P/poly muestra que existe una lista adecuada de valores a para cada tamaño de entrada, aunque encontrarla puede ser caro.

P/poly, a diferencia de otras clases de tiempo polinomial como P o BPP, generalmente no se considera una clase práctica para la computación. De hecho, contiene todos los lenguajes unarios indecidibles, ninguno de los cuales puede ser resuelto en general por computadoras reales. Por otro lado, si la longitud de entrada está limitada por un número relativamente pequeño y las cadenas de consejos son cortas, puede usarse para modelar algoritmos prácticos con una fase de preprocesamiento costosa separada y una fase de procesamiento rápido, como en el ejemplo anterior.

Importancia de P/poly

P / poly es una clase importante por varias razones. Para la informática teórica, hay varias propiedades importantes que dependen de P/poly:

Si NP ⊆ P/poly, entonces PH (la jerarquía polinómica) colapsa a $\Sigma _{2}^{\mathsf {P}}$ . Este resultado es el teorema de Karp-Lipton; además, NP ⊆ P/poly implica AM = MA^[4]
Si PSPACE ⊆ P / poly entonces ${\mathsf {PSPACE}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ , incluso PSPACE = MA .

Prueba: considere un lenguaje L de PSPACE. Se sabe que existe un sistema de prueba interactivo para L donde las acciones del probador pueden ser realizadas por una máquina PSPACE. Por supuesto, el probador puede ser reemplazado por un circuito de tamaño polinómico. Por lo tanto, L tiene un protocolo MA: Merlin envía el circuito como prueba, y Arthur puede simular el protocolo IP él mismo sin ninguna ayuda adicional.

Si P ^#P ⊆ P/poly entonces P^#P = MA.^[5] La prueba es similar a la anterior, basada en un protocolo interactivo para permanentes y #P-completitud de permanentes.
Si EXPTIME ⊆ P/poly entonces ${\mathsf {EXPTIME}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ (Teorema de Meyer), incluso EXPTIME = MA .
Si NEXPTIME ⊆ P/poly entonces NEXPTIME = EXPTIME, incluso NEXPTIME = MA . Por el contrario, NEXPTIME = MA implica NEXPTIME ⊆ P / poly ^[6]
Si EXP ^NP ⊆ P/poly entonces ${\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}$ (Buhrman, Homer)^[7]
Se sabe que MA _EXP, una versión exponencial de MA, no está contenida en P/poly .

Prueba: si MA _EXP ⊆ P/poly entonces PSPACE = MA (ver arriba). Haciendo padding, EXPSPACE = MA _EXP, por lo tanto EXPSPACE ⊆ P/poly pero esto puede demostrarse falso con la diagonalización.

Una de las razones más interesantes por las que P/poly es importante es la propiedad de que si NP no es un subconjunto de P/poly, entonces P ≠ NP. Esta observación fue el centro de muchos intentos de probar P ≠ NP . Se sabe que para un oráculo aleatorio A, NP ^A no es un subconjunto de P ^A/poly con probabilidad 1.^[1]

P/poly también se usa en el campo de la criptografía. La seguridad a menudo se define 'contra' los adversarios P/poly. Además de incluir la mayoría de los modelos prácticos de cómputo como BPP, esto también admite la posibilidad de que los adversarios puedan realizar una precomputación pesada para entradas de hasta una cierta longitud, como en la construcción de tablas arcoíris.

Aunque no todos los lenguajes en P/poly son lenguajes dispersos, existe una reducción de Turing en tiempo polinómico de cualquier idioma en P/poly a un idioma disperso.^[8]

El polinomio probabilístico de error acotado está contenido en P/poly

El teorema de Adleman establece que BPP ⊆ P/poly, donde BPP es el conjunto de problemas que se pueden resolver con algoritmos aleatorios con error de dos lados en el tiempo polinómico. Leonard Adleman demostró inicialmente un resultado más débil, a saber, que RP ⊆ P/poly;^[9] y este resultado se generalizó a BPP ⊆ P / poly por Bennett y Gill.^[10] Las variantes del teorema muestran que BPL está contenido en L/poly y AM está contenido en NP / poly .

Prueba

Sea L un lenguaje en BPP, y sea M (x, r) un algoritmo de tiempo polinómico que decida L con un error ≤ 1/3 (donde x es la cadena de entrada y r es un conjunto de bits aleatorios)

Construya una nueva máquina M' (x, R), que ejecute M 18*n veces y obtenga un voto mayoritario de los resultados (donde n es la longitud de entrada y R es una secuencia de 18*n rs independientemente aleatorios). Por lo tanto, M' también es tiempo polinomial y tiene una probabilidad de error ≤ 1/eⁿ por el límite de Chernoff. Si podemos arreglar R entonces obtenemos un algoritmo que es determinista.

Si Bad (x) se define como { R : M ' ( x, R ) es incorrecto}, tenemos:

\forall x\,{\mbox{Prob}}_{R}[R\in {\mbox{Bad}}(x)]\leq {\frac {1}{e^{n}}}.

El tamaño de entrada es n, por lo que hay 2ⁿ entradas posibles. Por lo tanto, por el límite de la unión, la probabilidad de que una R aleatoria sea mala para al menos una entrada x es

{\mbox{Prob}}_{R}[\exists x\,R\in {\mbox{Bad}}(x)]\leq {\frac {2^{n}}{e^{n}}}<1.

En palabras, la probabilidad de que R sea mala para algunas x es menor que 1, por lo tanto, debe haber una R que sea buena para todas las x. Tome esa R como la cadena de consejos en nuestro algoritmo P/poly .

Referencias

↑ ^a ^b Lutz, Jack H.; Schmidt, William J. (1993), «Circuit size relative to pseudorandom oracles», Theoretical Computer Science 107 (1): 95-119, doi:10.1016/0304-3975(93)90256-S .
↑ «Lecture notes on computational complexity by Peter Bro Miltersen». Archivado desde el original el 23 de febrero de 2012. Consultado el 25 de diciembre de 2009.
↑ Finding primes & proving primality
↑ Arvind, Vikraman; Köbler, Johannes; Schöning, Uwe; Schuler, Rainer (1995), «If NP has polynomial-size circuits, then MA = AM», Theoretical Computer Science 137 (2): 279-282, doi:10.1016/0304-3975(95)91133-B .
↑ Babai, László; Fortnow, Lance; Lund, Carsten (1991), «Nondeterministic exponential time has two-prover interactive protocols», Computational Complexity 1 (1): 3-40, doi:10.1007/BF01200056, archivado desde el original el 31 de marzo de 2012, consultado el 2 de octubre de 2011 .
↑ Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi (2002), «In search of an easy witness: exponential time vs. probabilistic polynomial time», Journal of Computer and System Sciences 65 (4): 672-694, doi:10.1016/S0022-0000(02)00024-7 .
↑ A Note on the Karp-Lipton Collapse for the Exponential Hierarchy
↑ Jin-Yi Cai. Lecture 11: P/poly, Sparse Sets, and Mahaney's Theorem. CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003.
↑ Adleman, L. M. (1978), «Two theorems on random polynomial time», Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science, pp. 75-83, doi:10.1109/SFCS.1978.37 .
↑ Charles H. Bennett, John Gill. Relative to a Random Oracle A, P^A ≠ NP^A ≠ co-NP^A with probability 1.

Datos: Q7117817

[lutz93-1] Lutz, Jack H.; Schmidt, William J. (1993), «Circuit size relative to pseudorandom oracles», Theoretical Computer Science 107 (1): 95-119, doi:10.1016/0304-3975(93)90256-S .

[2] «Lecture notes on computational complexity by Peter Bro Miltersen». Archivado desde el original el 23 de febrero de 2012. Consultado el 25 de diciembre de 2009.

[3] Finding primes & proving primality

[4] Arvind, Vikraman; Köbler, Johannes; Schöning, Uwe; Schuler, Rainer (1995), «If NP has polynomial-size circuits, then MA = AM», Theoretical Computer Science 137 (2): 279-282, doi:10.1016/0304-3975(95)91133-B .

[5] Babai, László; Fortnow, Lance; Lund, Carsten (1991), «Nondeterministic exponential time has two-prover interactive protocols», Computational Complexity 1 (1): 3-40, doi:10.1007/BF01200056, archivado desde el original el 31 de marzo de 2012, consultado el 2 de octubre de 2011 .

[6] Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi (2002), «In search of an easy witness: exponential time vs. probabilistic polynomial time», Journal of Computer and System Sciences 65 (4): 672-694, doi:10.1016/S0022-0000(02)00024-7 .

[7] A Note on the Karp-Lipton Collapse for the Exponential Hierarchy

[8] Jin-Yi Cai. Lecture 11: P/poly, Sparse Sets, and Mahaney's Theorem. CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003.

[9] Adleman, L. M. (1978), «Two theorems on random polynomial time», Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science, pp. 75-83, doi:10.1109/SFCS.1978.37 .

[10] Charles H. Bennett, John Gill. Relative to a Random Oracle A, P^A ≠ NP^A ≠ co-NP^A with probability 1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]