Usuario:Pablo Darko/BPP (clase de complejidad)

En teoría de la complejidad computacional BPP (tiempo polinomial probabilístico con error acotado) es la clase de problemas de decisión resolubles por una máquina de Turing probabilística en tiempo polinómico con una probabilidad de error acotada por 1/2 en todos los casos.

BPP es una de las clases de problemas prácticos más grandes, lo que significa que la mayor parte de los problemas de interés en BPP tienen un algoritmo probabilístico eficiente que puede ser ejecutado de forma eficiente en ordenadores reales modernos. BPP también contiene a P, la clase de problemas resolubles en tiempo polinómico por 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 producida Respuesta correcta	Sí	No
Sí	≥ 2/3	≤ 1/3
No	≤ 1/3	≥ 2/3
Algoritmo BPP (k ejecuciones)
Respuesta producida Respuesta correcta	Sí	No
Sí	> 1 − 2^−ck	< 2^−ck
No	< 2^−ck	> 1 − 2^−ck
para cierta constante c > 0

Informalmente, un problema está en BPP si existe un algoritmo para este que tiene las siguientes propiedades:

Puede lanzar monedas y tomar decisiones aleatorias
Su ejecución se realiza en tiempo polinomial en función del tamaño de la entrada en todos los casos
En cualquier ejecución del algoritmo tiene probabilidad de como mucho 1/3 de dar la respuesta incorrecta, independientemente de que sea SÍ o NO.

Definición

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

M se ejecuta en tiempo polinómico para todas las posibles entradas
Para cualquier x en L, M devuelve 1 con probabilidad mayor o igual a $2/3$
Para cualquier x que no esté en L, M devuelve 1 con probabilidad menor o igual a $1/3$

A diferencia de la clase de complejidad ZPP, es necesario que la máquina M se ejecute en tiempo polinómico en todos los casos, independientemente de los resultados aleatorios obtenidos.

Alternativamente, BPP puede ser definida utilizando sólo máquinas de Turing deterministas. Un lenguaje L está en BPP si y sólo si existe un polinomio p y una máquina de Turing determinista M tal que

M se ejecuta en tiempo polinómico para todas las posibles entradas
Para cualquier x en L, la fracción de palabras y de longitud p(|x|) que satisfacen $M(x,y)=1$ es mayor o igual a $2/3$
Para cualquier x que no esté en L, la fracción de palabras y de longitud p(|x|) que satisfacen $M(x,y)=1$ es menor o igual a $1/3$

En esta definición la palabra y se corresponde con los bits aleatorios que la máquina de Turing probabilística habría hecho. Esta definición es preferible en algunas aplicaciones ya que no hace mención a 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. Puede ser cualquier

Véase también

Heller, Hans (1986), «On relativized exponential and probabilistic complexity classes», Information and Control 71 (3): 231-243, doi:10.1016/S0019-9958(86)80012-2 .

RP
ZPP

Referencias

Valentine Kabanets (2003). "CMPT Teoría de 710 Complejidades: Conferencia 16". Universidad de Fraser del Simon.
Christos Papadimitriou (1993). Computational Complexity (1st edición). Addison Wesley. ISBN 0-201-53082-1.Christos Papadimitriou (1993). Computational Complexity (1st edición). Addison Wesley. ISBN 0-201-53082-1. Páginas 257@–259 de sección 11.3: Fuentes Aleatorias. Páginas 269@–271 de sección 11.4: complejidad de Circuito.
Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Sección 10.2.1: La clase BPP, pp. 336@–339.
Karpinski, Marek; Verbeek, Rutger (1987). «Randomness, provability and the separation of Monte Carlo Time and space». Lecture Notes in Computer Science 270: 189-207.Karpinski, Marek; Verbeek, Rutger (1987). «Randomness, provability and the separation of Monte Carlo Time and space». Lecture Notes in Computer Science 270: 189-207. : 189@–207.
Arora, Sanjeev; Boaz Barak (2009). "Complejidad computacional: Una Aproximación Moderna".

Enlaces externos