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 se pueden resolver mediante una máquina de Turing probabilística en tiempo polinomial con una probabilidad de error acotada por 1/3 para todas las instancias. BPP es una de las clases prácticas de problemas 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 contiene P , la clase de problemas que se pueden resolver en tiempo polinomial con una máquina determinista, ya que una máquina determinista es un caso especial de una máquina probabilística.
De manera informal, un problema está en BPP si existe un algoritmo para él que tiene las siguientes propiedades:
Un lenguaje L está en BPP si y sólo si existe una máquina de Turing probabilística M , tal que
A diferencia de la clase de complejidad ZPP , se requiere que la máquina M funcione durante un tiempo polinomial en todas las entradas, independientemente del resultado de los lanzamientos aleatorios de monedas.
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
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 (exclusivo) en lugar de 1/3 no cambiaría el conjunto resultante BPP . Por ejemplo, si uno definiera la clase con la restricción de que el algoritmo puede estar equivocado con una probabilidad de como máximo 1/2 100 , 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 el 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]
Obviamente, todos los problemas en P también están en BPP . Sin embargo, se sabe que muchos problemas están en BPP pero no en P. El número de estos problemas está disminuyendo y se conjetura que P = BPP .
Durante mucho tiempo, uno de los problemas más famosos que se sabía que estaba en BPP pero no se sabía que estaba en 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 de tiempo polinomial determinista para este problema, demostrando así que está en P .
Un ejemplo importante de un problema en BPP (de hecho en co-RP ) que aún no se sabe que esté en P es la prueba de identidad polinomial , 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, ¿hay una asignación de valores a las variables tal que cuando se evalúa un polinomio distinto de cero en estos valores, el resultado es distinto de cero? Basta con elegir el valor de cada variable de manera uniforme 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 por una computadora cuántica , obtenemos la clase BQP .
Al agregar poselección a BPP , o permitir que las rutas de cálculo tengan diferentes longitudes, se obtiene 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 que tiene probabilidades de ser correcto. Los problemas de la clase BPP tienen algoritmos de Monte Carlo con un tiempo de ejecución limitado por polinomios. Esto se compara con un algoritmo de Las Vegas , que es un algoritmo aleatorio que genera la respuesta correcta o genera un "error" con baja probabilidad. Los algoritmos de Las Vegas con tiempos de ejecución limitados por polinomios se utilizan para definir la clase ZPP . Alternativamente, ZPP contiene algoritmos probabilísticos que siempre son correctos y tienen un tiempo de ejecución polinomial esperado. Esto es más débil que decir que es un algoritmo de tiempo polinomial, ya que puede ejecutarse durante un tiempo superpolinomial, pero con una probabilidad muy baja.
Se sabe que BPP es cerrado bajo complemento ; es decir, BPP = co-BPP . BPP es bajo por sí mismo, lo que significa que una máquina BPP con el poder de resolver problemas BPP instantáneamente (una máquina oráculo BPP ) no es más poderosa que la máquina sin este poder adicional. En símbolos, BPP BPP = BPP .
La relación entre BPP y NP es desconocida: no se sabe si BPP es un subconjunto de NP , NP es un subconjunto de BPP o ninguno de los dos. Si NP está contenido en BPP , lo que 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 esos 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 . Como resultado, P = NP conduce a P = BPP ya que PH colapsa a P en este caso. Por lo tanto, o bien P = BPP o bien P ≠ NP o ambos.
El teorema de Adleman establece 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 prueba de este hecho, cada algoritmo BPP que opera en 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 clase BPP es cerrada bajo complementación, unión e intersección.
En relación con los oráculos, sabemos que existen oráculos A y B, tales que P A = BPP A y P B ≠ BPP B . Además, en relación con un oráculo aleatorio con probabilidad 1, P = BPP y BPP está estrictamente contenido en NP y co-NP . [6]
Incluso hay un oráculo en el que (y por lo tanto ), [7] que puede construirse iterativamente de la siguiente manera. Para un problema completo E NP (relativizado) fijo, el oráculo dará respuestas correctas con alta probabilidad si se consulta con la instancia del problema seguida de una cadena aleatoria de longitud kn ( n es la longitud de la instancia; k es una constante pequeña apropiada). Comience con n = 1. Para cada instancia del problema de longitud n, arregle las respuestas del oráculo (vea el lema a continuación) para arreglar la salida de la instancia. A continuación, proporcione las salidas de la instancia para las consultas que consisten en la instancia seguida de la cadena de longitud kn , y luego trate la salida para las consultas de longitud ≤ ( k +1) n como fija, y continúe con las instancias de longitud n +1.
Lema — Dado un problema (específicamente, un código de máquina de oráculo y una restricción de tiempo) en E NP relativizado , para cada oráculo parcialmente construido y entrada de longitud n , la salida se puede fijar especificando 2 O ( n ) respuestas de oráculo.
La máquina se simula y las respuestas del oráculo (que no están ya fijadas) se fijan paso a paso. Hay como máximo una consulta de oráculo por paso de cálculo determinista. Para el oráculo NP relativizado, si es posible, fije la salida para que sea sí eligiendo una ruta de cálculo y fijando las respuestas del oráculo base; de lo contrario, no es necesario realizar ninguna fijación y, de cualquier manera, hay como máximo 1 respuesta del oráculo base por paso. Dado que hay 2 pasos O ( n ) , se deduce el lema.
El lema asegura que (para un k suficientemente grande ), es posible hacer la construcción dejando suficientes cadenas para las respuestas E NP relativizadas . Además, podemos asegurar que para el E NP relativizado , el tiempo lineal es suficiente, incluso para problemas de función (si se da un oráculo de función y un tamaño de salida lineal) y con una probabilidad de error exponencialmente pequeña (con exponente lineal). Además, esta construcción es efectiva porque dado un oráculo arbitrario A podemos organizar el oráculo B para que tenga P A ≤ P B y EXP NP A = EXP NP B = BPP B . Además, para un oráculo ZPP =EXP (y por lo tanto ZPP=BPP=EXP<NEXP ), uno fijaría las respuestas en el cálculo E relativizado a una respuesta no válida especial, asegurando así que no se den respuestas falsas.
La mayoría de los expertos en la materia conjeturan la existencia de ciertos generadores de números pseudoaleatorios potentes . Dichos generadores podrían reemplazar a los números aleatorios verdaderos en cualquier algoritmo aleatorio en tiempo polinomial, produciendo resultados indistinguibles. La conjetura de que estos generadores existen implica que la aleatoriedad no otorga poder computacional adicional al cálculo en tiempo polinomial, es decir, P = RP = BPP . Más firmemente, la suposición de que P = BPP es en cierto sentido equivalente a la existencia de generadores de números pseudoaleatorios potentes. [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]
La clase io-SUBEXP , que significa infinitamente a menudo SUBEXP , contiene problemas que tienen algoritmos de tiempo subexponencial para una cantidad infinita de 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, tenga en cuenta que generalmente se conjetura que la jerarquía de tiempo exponencial no colapsa.
Russell Impagliazzo y Avi Wigderson demostraron que si hubiera algún problema en E , donde
tiene una complejidad de circuito de 2 Ω( n ), entonces P = BPP . [10]
