En la teoría de la complejidad computacional , el tiempo polinomial probabilístico de error acotado ( BPP ) 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 acotada de 1/3 para todos los casos. 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 polinómico con una máquina determinista, ya que una máquina determinista es un caso especial de una máquina probabilística.
Algoritmo BPP (1 ejecución) | ||
---|---|---|
Respuesta producido Respuesta correcta | sí | No |
sí | ≥ 2/3 | ≤ 1/3 |
No | ≤ 1/3 | ≥ 2/3 |
Algoritmo BPP ( k ejecuciones) | ||
Respuesta producido Respuesta correcta | sí | No |
sí | > 1-2 - ck | <2 - ck |
No | <2 - ck | > 1-2 - ck |
para alguna constante c > 0 |
De manera informal, un problema está en BPP si hay un algoritmo para él que tiene las siguientes propiedades:
- Está permitido lanzar monedas y tomar decisiones al azar.
- Se garantiza que se ejecuta en tiempo polinomial.
- En cualquier ejecución dada del algoritmo, tiene una probabilidad de como máximo 1/3 de dar una respuesta incorrecta, ya sea que la respuesta sea SÍ o NO.
Definición
Una lengua L está en BPP si y solo 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 mayor o igual a 2/3
- Para todo x no en L , M produce 1 con probabilidad menor 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 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 es mayor o igual a 2/3
- Para todo x que no esté en L , la fracción de cadenas y de longitud p (| x |) que satisfacen es menor 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 probabilística de Turing. Para algunas aplicaciones, esta definición es preferible ya que no menciona las máquinas probabilísticas de Turing.
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 de BPP resultante . Por ejemplo, si uno define la clase con la restricción de que el algoritmo puede estar equivocado con una probabilidad de 1/2 100 como máximo , 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 utilizar el resultado mayoritario de las ejecuciones para obtener un algoritmo más preciso. La probabilidad de que la mayoría de las carreras sean incorrectas disminuye exponencialmente como consecuencia del límite de Chernoff . [1]
Problemas
Todos los problemas en P están obviamente también en BPP . Sin embargo, muchos problemas han sido conocidos por ser en BPP , pero no se sabe que es 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 primo . Sin embargo, en los artículo de 2002 Primes está en P , Manindra Agrawal y sus estudiantes Neeraj Kayal y Nitin Saxena encontraron un algoritmo de tiempo polinomial determinista para este problema, lo cual demuestra que se trata de P .
Un ejemplo importante de un problema en BPP (de hecho en co-RP ) 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, ¿existe una asignación de valores a las variables de manera que cuando se evalúe un polinomio distinto de cero en estos valores, el resultado sea distinto de cero? Basta elegir el valor de cada variable uniformemente al azar de un subconjunto finito de al menos d valores para lograr la probabilidad de error acotada, donde d es el grado total del polinomio. [2]
Clases relacionadas
Si el acceso a la aleatoriedad se retira 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 cálculo tengan diferentes longitudes, da la ruta de clase BPP . [3] Se sabe que la ruta de BPP contiene NP , y está contenida en su contraparte cuántica 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 da como resultado la respuesta correcta o "falla" con baja probabilidad. Los algoritmos de Las Vegas con tiempos de ejecución ligados a 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 polinómico 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.
Propiedades teóricas de la complejidad
Se sabe que BPP se cierra 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 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 poco probable 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 polinomial 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, P = BPP o P ≠ NP o ambos.
El teorema de Adleman establece que la pertenencia a cualquier lenguaje en BPP puede ser determinada por 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 limitada puede ser desaleatorizado en un algoritmo determinista usando una cadena fija de bits aleatorios. Sin embargo, encontrar esta cuerda puede resultar caro. Karpinski y Verbeek (1987a) demostraron algunos resultados débiles de separación para las clases de tiempo de Montecarlo ; véase también Karpinski y Verbeek (1987b) .
Propiedades de cierre
La clase BPP está cerrada bajo complementación, unión e intersección.
Relativización
En relación con oráculos, sabemos que existen oráculos A y B, de tal manera 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 BPP = EXP NP (y por lo tanto P
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 arreglar especificando 2 O ( n ) respuestas de oráculo.
Prueba: la máquina se simula y las respuestas de Oracle (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, 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 corregirlo, y de cualquier manera hay como máximo 1 respuesta del oráculo base por paso. Dado que hay 2 O ( n ) pasos, el lema sigue.
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 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 eficaz en el que dado un oráculo A arbitraria podemos organizar el oráculo B tener 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
Desaleatorización
La existencia de ciertos fuertes generadores de números pseudoaleatorios se conjeturó por la mayoría de los expertos del campo. 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). [ cita requerida ]
László Babai , Lance Fortnow , Noam Nisan y Avi Wigderson demostraron que, a menos que EXPTIME colapse en MA , BPP está contenido en [8]
La clase io-SUBEXP , que significa infinitamente SUBEXP , contiene problemas que tienen algoritmos de tiempo sub-exponenciales para infinitos tamaños de entrada. También mostraron 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 por lo general 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 , ¿dónde
tiene una complejidad de circuito 2 Ω ( n ) entonces P = BPP . [9]
Ver también
- RP
- ZPP
- BQP
- Lista de clases de complejidad
Referencias
- ^ Valentine Kabanets, CMPT 710 - Teoría de la complejidad: Conferencia 16 , 28 de octubre de 2003
- ^ Madhu Sudan y Shien Jin Ong. Instituto de Tecnología de Massachusetts: 6.841 / 18.405J Teoría de la complejidad avanzada: Clase 6: Algoritmos aleatorios, propiedades de BPP . 26 de febrero de 2003.
- ^ BPPpath Archivado 2013-06-03 en Wayback Machine en Complexity Zoo Archivado 2019-08-27 en Wayback Machine
- ^ Lance Fortnow y Bill Gasarch, Sacando la Quantumness , 20 de diciembre de 2005
- ^ Adleman, LM (1978). "Dos teoremas sobre el tiempo polinomial aleatorio". Actas del XIX Simposio Anual del IEEE sobre Fundamentos de la Computación . págs. 75–83.
- ^ Bennett, Charles H .; Gill, John (1981), "Relative to a Random Oracle A, P ^ A! = NP ^ A! = Co-NP ^ A with Probability 1", SIAM Journal on Computing , 10 (1): 96-113, doi : 10.1137 / 0210008 , ISSN 1095-7111
- ^ Heller, Hans (1986), "Sobre clases de complejidad relativizadas exponenciales y probabilísticas", Información y control , 71 (3): 231–243, doi : 10.1016 / S0019-9958 (86) 80012-2
- ^ Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi (1993). " BPP tiene simulaciones de tiempo subexponenciales a menos que EXPTIME tenga pruebas publicables". Complejidad computacional . 3 : 307–318. doi : 10.1007 / bf01275486 .
- ^ Russell Impagliazzo y Avi Wigderson (1997). " P = BPP si E requiere circuitos exponenciales: desaleatorizar el lema XOR". Actas del vigésimo noveno simposio anual de ACM sobre teoría de la computación , págs. 220–229. doi : 10.1145 / 258533.258590
- Valentine Kabanets (2003). "CMPT 710 - Teoría de la complejidad: Clase 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 del circuito.
- Michael Sipser (1997). Introducción a la Teoría de la Computación . Publicación de PWS. 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 separación del tiempo y el espacio de Montecarlo". Apuntes de conferencias en Ciencias de la Computación . 270 : 189-207.
- Karpinski, Marek ; Verbeek, Rutger (1987b). "En el espacio de Monte Carlo funciones construibles y resultados de separación para clases de complejidad probabilística" . Información y Computación . 75 (2): 178–189. doi : 10.1016 / 0890-5401 (87) 90057-5 .
- Arora, Sanjeev; Boaz Barak (2009). "Complejidad computacional: un enfoque moderno".
enlaces externos
- Princeton CS 597E: lista de documentos de desaleatorización
- Harvard CS 225: Pseudoaleatoriedad Archivado el 05 de agosto de 2003 en la Wayback Machine.