BPP (complejidad)
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 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 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.
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 , tal que
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 uno definiera la clase con la restricción de que el algoritmo puede estar equivocado con una probabilidad máxima de 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 ces cualquier constante positiva, y n es la longitud de 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 . [1]
