BPP (complejidad)

En la teoría de la complejidad computacional , una rama de la informática, el tiempo polinomial probabilístico de error acotado ( BPP ) es la clase de problemas de decisión que una máquina de Turing probabilística puede resolver en tiempo polinomial con una probabilidad de error acotada por 1/3 para todas las instancias. BPP es una de las clases de problemas prácticos más grandes , lo que significa que la mayoría de los problemas de interés en BPP tienen algoritmos probabilísticos eficientes que se pueden ejecutar rápidamente en máquinas modernas reales. BPP también incluye P , la clase de problemas que se pueden resolver en tiempo polinomial con una máquina determinista, ya que un algoritmo determinista es un caso especial de un algoritmo probabilístico.

De manera informal, un problema pertenece al BPP si existe un algoritmo para él que tiene las siguientes propiedades:

• Está permitido lanzar monedas y tomar decisiones al azar.
• Se garantiza que se ejecutará en tiempo polinomial.
• En cualquier ejecución del algoritmo, existe una probabilidad máxima de 1/3 de que dé una respuesta incorrecta, ya sea SÍ o NO.

Un lenguaje L está en BPP 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 mayor o igual a 2/3.
• Para todo x que no pertenece a L , M produce 1 con una probabilidad menor o igual a 1/3.

A diferencia de la clase de complejidad ZPP , la máquina M debe ejecutarse en tiempo polinomial para todas las entradas, independientemente del resultado de los lanzamientos aleatorios de moneda.

Alternativamente, BPP puede definirse utilizando únicamente máquinas de Turing deterministas. Un lenguaje L está en BPP 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 ⁠${\displaystyle M(x,y)=1}$es mayor o igual que 2/3
• Para todo x que no está en L , la fracción de cadenas y de longitud p (| x |) que satisfacen ⁠${\displaystyle M(x,y)=1}$es menor o igual que 1/3

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. Para algunas aplicaciones, esta definición es preferible, ya que no menciona las máquinas de Turing probabilísticas.

En la práctica, una probabilidad de error de 1/3 podría no ser aceptable; sin embargo, la elección de 1/3 en la definición es arbitraria. Modificar la definición para usar cualquier constante entre 0 y 1/2 (exclusiva) en lugar de 1/3 no cambiaría el conjunto BPP resultante . Por ejemplo, si se definiera la clase con la restricción de que el algoritmo puede equivocarse con una probabilidad máxima de 1/2 ¹⁰⁰ , esto daría como resultado la misma clase de problemas. La probabilidad de error ni siquiera tiene que ser constante: la misma clase de problemas se define permitiendo un error tan alto como 1/2 − n ^{− c} , por un lado, o requiriendo un error tan pequeño como 2 ^{− n c} , por otro lado, donde c es cualquier constante positiva y n es la longitud de la entrada. Esta flexibilidad en la elección de la probabilidad de error se basa en la idea de ejecutar un algoritmo propenso a errores muchas veces y usar el resultado mayoritario de las ejecuciones para obtener un algoritmo más preciso. La probabilidad de que la mayoría de las ejecuciones sean erróneas disminuye exponencialmente como consecuencia del límite de Chernoff . ^{[ 1 ]}

Problema sin resolver en informática

⁠${\displaystyle {\mathsf {P}}{\overset {?}{=}}{\mathsf {BPP}}}$⁠

Más problemas sin resolver en informática

Obviamente, todos los problemas de P también pertenecen a BPP . Sin embargo, se sabe que muchos problemas pertenecen a BPP pero no a P. El número de tales problemas está disminuyendo, y se conjetura que P = BPP .

Durante mucho tiempo, uno de los problemas más famosos que se sabía que pertenecían a BPP pero que no se sabía que pertenecían a P era el problema de determinar si un número dado es primo . Sin embargo, en el artículo de 2002 PRIMES is in P , Manindra Agrawal y sus estudiantes Neeraj Kayal y Nitin Saxena encontraron un algoritmo determinista de tiempo polinomial para este problema, demostrando así que pertenece a P.

Un ejemplo importante de un problema en BPP (de hecho, en co-RP ) que aún no se sabe que exista en P es la prueba de identidad polinómica , el problema de determinar si un polinomio es idénticamente igual al polinomio cero, cuando se tiene acceso al valor del polinomio para cualquier entrada dada, pero no a los coeficientes. En otras palabras, ¿existe una asignación de valores a las variables tal que cuando se evalúa un polinomio no nulo sobre estos valores, el resultado sea distinto de cero? Basta con elegir el valor de cada variable uniformemente al azar de un subconjunto finito de al menos d valores para lograr una probabilidad de error acotada, donde d es el grado total del polinomio. ^{[ 2 ]}

Si se elimina el acceso a la aleatoriedad de la definición de BPP , obtenemos la clase de complejidad P. En la definición de la clase, si reemplazamos la máquina de Turing ordinaria con una computadora cuántica , obtenemos la clase BQP .

Agregar postselección a BPP , o permitir que las rutas de computación tengan diferentes longitudes, da como resultado la clase BPP _path . ^{[ 3 ]} Se sabe que BPP _path contiene NP , y está contenido en su contraparte cuántica PostBQP .

Un algoritmo de Monte Carlo es un algoritmo aleatorio con alta probabilidad de éxito. Los problemas de la clase BPP utilizan algoritmos de Monte Carlo con un tiempo de ejecución polinomial. Esto contrasta con un algoritmo de Las Vegas , un algoritmo aleatorio que, con baja probabilidad, devuelve la respuesta correcta o un resultado de "fallo". Los algoritmos de Las Vegas con tiempos de ejecución polinomiales se utilizan para definir la clase ZPP . Alternativamente, ZPP incluye algoritmos probabilísticos que siempre son correctos y tienen un tiempo de ejecución polinomial esperado. Esta definición es menos precisa que la de un algoritmo de tiempo polinomial, ya que puede ejecutarse en tiempo superpolinomial, pero con muy baja probabilidad.

Se sabe que BPP es cerrado bajo complemento ; es decir, BPP = co-BPP . BPP es bajo para sí mismo, lo que significa que una máquina BPP con la capacidad de resolver problemas BPP instantáneamente (una máquina oráculo BPP ) no es más potente que la máquina sin esta capacidad adicional. En símbolos, BPP ^BPP = BPP .

Se desconoce la relación entre BPP y NP : no se sabe si BPP es un subconjunto de NP , si NP es un subconjunto de BPP o si ninguna de las dos cosas. Si NP está contenido en BPP , lo cual se considera improbable ya que implicaría soluciones prácticas para problemas NP-completos , entonces NP = RP y PH ⊆ BPP . ^{[ 4 ]}

Se sabe que RP es un subconjunto de BPP , y BPP es un subconjunto de PP . No se sabe si estos dos son subconjuntos estrictos, ya que ni siquiera sabemos si P es un subconjunto estricto de PSPACE . BPP está contenido en el segundo nivel de la jerarquía polinómica y, por lo tanto, está contenido en PH . Más precisamente, el teorema de Sipser-Lautemann establece que${\displaystyle {\mathsf {BPP}}\subseteq \Sigma _{2}\cap \Pi _{2}}$Como resultado, P = NP conduce a P = BPP ya que PH se reduce a P en este caso. Por lo tanto, o P = BPP o P ≠ NP o ambas cosas.

El teorema de Adleman afirma que la pertenencia a cualquier lenguaje en BPP puede determinarse mediante una familia de circuitos booleanos de tamaño polinomial , lo que significa que BPP está contenido en P/poly . ^{[ 5 ]} De hecho, como consecuencia de la demostración de este hecho, todo algoritmo BPP que opera sobre entradas de longitud acotada puede desaleatorizarse en un algoritmo determinista utilizando una cadena fija de bits aleatorios. Sin embargo, encontrar esta cadena puede ser costoso. Karpinski y Verbeek (1987a) demostraron algunos resultados de separación débil para clases de tiempo de Monte Carlo ; véase también Karpinski y Verbeek (1987b) .

La mayoría de los expertos en el campo conjeturan la existencia de ciertos generadores de números pseudoaleatorios robustos. Dichos generadores podrían reemplazar a los números aleatorios verdaderos en cualquier algoritmo aleatorio de tiempo polinomial, produciendo resultados indistinguibles. La conjetura de que estos generadores existen implica que la aleatoriedad no proporciona potencia computacional adicional a la computación de tiempo polinomial, es decir, P = RP = BPP . Más aún , la suposición de que P = BPP es, en cierto sentido, equivalente a la existencia de generadores de números pseudoaleatorios robustos. ^{[ 8 ]}

László Babai , Lance Fortnow , Noam Nisan y Avi Wigderson demostraron que a menos que EXPTIME colapse a MA , BPP está contenido en ^{[ 9 ].}

${\displaystyle {\textsf {io-SUBEXP}}=\bigcap \nolimits _{\varepsilon >0}{\textsf {io-DTIME}}\left(2^{n^{\varepsilon }}\right).}$

La clase io-SUBEXP , que significa SUBEXP infinitamente frecuente , contiene problemas que tienen algoritmos de tiempo subexponencial para infinitos tamaños de entrada. También demostraron que P = BPP si la jerarquía de tiempo exponencial, que se define en términos de la jerarquía polinómica y E como E ^PH , colapsa a E ; sin embargo, cabe señalar que la jerarquía de tiempo exponencial generalmente se conjetura que no colapsa.

Russell Impagliazzo y Avi Wigderson demostraron que si hay algún problema en E , donde

${\displaystyle {\mathsf {E}}={\mathsf {DTIME}}\left(2^{O(n)}\right),}$

tiene una complejidad de circuito de 2 ^{Ω( n )} entonces P = BPP . ^{[ 10 ]}

• rol
• ZPP
• BQP
• Lista de clases de complejidad

• Valentine Kabanets (2003). "CMPT 710 – Teoría de la complejidad: Lección 16". Universidad Simon Fraser .
• Christos Papadimitriou (1993). Complejidad computacional (1.ª  ed.). Addison Wesley. ISBN 0-201-53082-1.Páginas 257–259 de la sección 11.3: Fuentes aleatorias. Páginas 269–271 de la sección 11.4: Complejidad de circuitos.
• Michael Sipser (1997). Introducción a la teoría de la computación . PWS Publishing. ISBN 0-534-94728-X.Sección 10.2.1: La clase BPP, págs.  336–339.
• Karpinski, Marek ; Verbeek, Rutger (1987a). "Aleatoriedad, demostrabilidad y la separación del tiempo y el espacio de Monte Carlo". En Börger, Egon (ed.). Teoría de la computación y lógica, en memoria de Dieter Rödding . Lecture Notes in Computer Science. Vol.  270. Springer. pp. 189–207 . doi : 10.1007/3-540-18170-9_166 . 
• Karpinski, Marek ; Verbeek, Rutger (1987b). "Sobre las funciones construibles en el espacio de Monte Carlo y los resultados de separación para clases de complejidad probabilística" . Information and Computation . 75 (2): 178–189 . doi : 10.1016/0890-5401(87)90057-5 .
• Arora, Sanjeev; Boaz Barak (2009). "Complejidad computacional: un enfoque moderno".

• Lista de trabajos sobre desaleatorización para la asignatura CS 597E de Princeton
• Harvard CS 225: Pseudorandomness. Archivado el 5 de agosto de 2003 en Wayback Machine.