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 se pueden resolver mediante una máquina de Turing probabilística en tiempo polinomial con una probabilidad de error limitada 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 situaciones reales. máquinas modernas. 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.

Informalmente, un problema está en BPP si hay un algoritmo para él que tiene las siguientes propiedades:

• Se permite cambiar monedas y tomar decisiones aleatorias
• Está garantizado que funcione en tiempo polinomio
• En cualquier ejecución dada del algoritmo, tiene una probabilidad de al menos 1/3 de dar la respuesta incorrecta, ya sea SI o NO.

Definición

Un lenguaje L está en BPP si y solo si existe una máquina de Turing probabilística M, tal que

• M se ejecuta para el tiempo polinomio en todas las entradas
• Para todos x dentro L, M productos 1 con probabilidad superior o igual a 2/3
• Para todos x no en L, M productos 1 con probabilidad inferior o igual a 1/3

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 se puede definir utilizando solo 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 ese

• M se ejecuta para el tiempo polinomio en todas las entradas
• Para todos x dentro L, la fracción de cuerdas Sí. de longitud p(en inglés)xi) Que satisfacen M()x,Sí.)=1{displaystyle M(x,y)=1} es mayor o igual a 2/3
• Para todos x no en L, la fracción de cuerdas Sí. de longitud p(en inglés)xi) Que satisfacen M()x,Sí.)=1{displaystyle M(x,y)=1} es inferior o igual a 1/3

En esta definición, la cadena y corresponde a la salida de los lanzamientos aleatorios de monedas que habría hecho 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 se define la clase con la restricción de que el algoritmo puede fallar 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^−nc 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 utilizar el resultado mayoritario de las ejecuciones para obtener un algoritmo más preciso. La probabilidad de que la mayoría de las ejecuciones sean incorrectas disminuye exponencialmente como consecuencia del límite de Chernoff.

Problemas

Todos los problemas en P obviamente 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 tales problemas está disminuyendo y se conjetura que P = BPP.

Durante mucho tiempo, uno de los problemas más famosos que se sabe que está en BPP pero que no se sabe que está en P fue el problema de determinar si un número dado es principal. Sin embargo, en el artículo de 2002 PRIMES is in P, Manindra Agrawal y sus alumnos Neeraj Kayal y Nitin Saxena encontraron un algoritmo de tiempo polinomial determinista para este problema, mostrando 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 identidad polinomial prueba, el problema de determinar si un polinomio es idénticamente igual al polinomio cero, cuando 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 distinto de cero en estos valores, el resultado es 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 de el polinomio

Clases relacionadas

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 una selección posterior a BPP, o permitir que las rutas de cálculo tengan diferentes longitudes, da la clase BPP_ruta. Se sabe que BPP_path contiene NP, y está contenido en su homólogo cuántico PostBQP.

Un algoritmo de Monte Carlo es un algoritmo aleatorio que probablemente sea correcto. Los problemas de la clase BPP tienen algoritmos de Monte Carlo con tiempo de ejecución acotado 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 "fallido" con baja probabilidad. Los algoritmos de Las Vegas con tiempos de ejecución polinomiales 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 polinómico, ya que puede ejecutarse durante un tiempo superpolinomial, pero con una probabilidad muy baja.

Propiedades teóricas de la complejidad

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

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 de BPP instantáneamente (un BPP oracle machine) no es más poderosa que la máquina sin esta potencia extra. 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 >, NP es un subconjunto de BPP o ninguno. 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.

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 PSPACE. BPP está contenida en el segundo nivel de la jerarquía polinómica y por lo tanto está contenida en PH. Más precisamente, el teorema Sipser-Lautemann afirma que BPP⊆ ⊆ .. 2∩ ∩ ▪ ▪ 2{displaystyle {Mathsf {BPP}subseteq Sigma _{2}cap Pi _{2}. Como resultado, P = NP conduce a P = BPP desde entonces PH colapsos a P en este caso. Así o P = BPP o P ل NP o ambos.

El teorema de Adleman establece que la pertenencia a cualquier idioma en BPP puede determinarse mediante una familia de circuitos booleanos de tamaño polinomial, lo que significa que BPP está contenido en P/poliéster. De hecho, como consecuencia de la prueba de este hecho, todo algoritmo BPP que opere con entradas de longitud acotada se puede convertir en un algoritmo determinista utilizando una cadena fija de bits aleatorios. Sin embargo, encontrar esta cadena puede ser costoso. Karpinski & Verbeek (1987a), véase también Karpinski & Verbeek (1987b).

Propiedades de cierre

La clase BPP es cerrada bajo complementación, unión e intersección.

Relativización

En relación a los oráculos, sabemos que existen los 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.

Incluso hay un oráculo en el que BPP=EXP^NP (y por lo tanto P<NP<BPP=EXP=NEXP), que se puede construir iterativamente de la siguiente manera. Para un problema completo fijo E^NP (relativizado), 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 pequeña constante apropiada). Comienza con n=1. Para cada instancia del problema de la longitud n corrija las respuestas de Oracle (consulte el lema a continuación) para corregir la salida de la instancia. A continuación, proporcione los resultados de la instancia para las consultas que consistan en la instancia seguida de una cadena de longitud kn y, a continuación, trate la salida para las consultas de longitud ≤(k+1) n como fijo, y continúe con las instancias de longitud n+1.

Lema: dado un problema (específicamente, un código de máquina de Oracle 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 arreglar especificando 2^O(n) respuestas de Oracle.
Prueba: La máquina está simulada y las respuestas del oráculo (que aún no están arregladas) se arreglan paso a paso. Hay como máximo una consulta de Oracle por paso de cálculo determinista. Para el oráculo NP relativizado, si es posible, corrija la salida para que sea sí eligiendo una ruta de cálculo y corrigiendo las respuestas del oráculo base; de lo contrario, no es necesario corregir, y de cualquier manera, hay como máximo 1 respuesta del oráculo base por paso. Como hay 2^O(n) pasos, el lema sigue.

El lema asegura que (para un k lo 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 le 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 A arbitrario, podemos organizar el oráculo B para que tenga P^A≤P^B y EXP^NPA =EXP^NPB=BPP^B. Además, para un oráculo ZPP=EXP (y, por lo tanto, ZPP=BPP=EXP<NEXP), uno arreglaría las respuestas en el cálculo E relativizado a una no respuesta especial, asegurando así que no se den respuestas falsas.

Desaleatorización

La mayoría de los expertos en la materia conjeturan la existencia de ciertos generadores de números pseudoaleatorios potentes. Esta conjetura implica que la aleatoriedad no otorga poder computacional adicional al cálculo del tiempo polinomial, es decir, P = RP = BPP. Tenga en cuenta que los generadores ordinarios no son suficientes para mostrar este resultado; cualquier algoritmo probabilístico implementado usando un generador de números aleatorios típico siempre producirá resultados incorrectos en ciertas entradas independientemente de la semilla (aunque estas entradas pueden ser raras).

László Babai, Lance Fortnow, Noam Nisan y Avi Wigderson demostraron que, a menos que EXPTIME colapse a MA, BPP está contenido en

0}{textsf {i.o.-DTIME}}left(2^{n^{varepsilon }}right).}" xmlns="http://www.w3.org/1998/Math/MathML">i.o.-SUBEXP=⋂ ⋂ ε ε ■0i.o.-DTIME()2nε ε ).{displaystyle {textsf {i.o.-SUBEXP}=bigcap nolimits _{varepsilon ¿Qué? }0}{textsf {i.o.-DTIME}}left(2^{n^{varepsilon }}right).}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f52790872474726ec0b3d32fcbe760d5bfcfafac" style="vertical-align: -1.838ex; width:40.298ex; height:4.843ex;"/>

La clase i.o.-SUBEXP, que significa infinitamente a menudo SUBEXP, contiene problemas que tienen algoritmos de tiempo subexponenciales 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 polinomial 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 colapsará.

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

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

tiene una complejidad de circuito de 2^Ω(n) entonces P = BPP.