Probar o refutar: BPP (0.90,0.95) = BPP

Realmente me gustaría su ayuda para probar o refutar la siguiente afirmación: . En la teoría de la complejidad computacional, BPP, que significa tiempo polinómico probabilístico de error limitado, es la clase de problemas de decisión que puede resolver una máquina de Turing probabilística en tiempo polinómico, con una probabilidad de error de como máximo para todas las instancias . .$BPP(0.90,0.95)=BPP$$\frac{1}{3}$$BPP=BPP(\frac{1}{3},\frac{2}{3})$

No es inmediato que ninguno de los conjuntos sea un subconjunto del otro, ya que si la probabilidad de un error es menor que , no tiene que ser menor que y si es mayor que no tiene que ser mayor que .$0.9$$\frac{1}{3}$$\frac{2}{3}$$0.905$

Estoy tratando de usar la desigualdad de Chernoff para probar la afirmación, no estoy seguro exactamente cómo. Realmente me gustaría tu ayuda. ¿Hay alguna afirmación general sobre estas relaciones que pueda usar?

Para ampliar mi comentario en una respuesta: la forma multiplicativa del límite de Chernoff dice que si la expectativa para la suma de variables binarias aleatorias independientes es , entonces la probabilidad de desviarse ' demasiado lejos 'de esa expectativa va como: .$X=\sum_{i=0}^n X_i$$\mu$$Pr(X\gt (1+\delta)\mu) \lt \left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu$

Ahora, imagine un procedimiento en el que, dada una cadena para probar, ejecutamos pruebas de nuestro algoritmo (para que se elija alguna más adelante) y acepte si al menos de esas pruebas aceptan . Podemos usar el límite de Chernoff para encontrar la probabilidad de falla en términos de siguiente manera:$\sigma$$n$$BPP(0.90, 0.95)$$n$$0.925n$$\sigma$$n$

Supongamos que denota el resultado de la ésima prueba y, por lo tanto, el número de pruebas que tienen éxito. Podemos suponer conservadoramente que nuestra probabilidad de falsos positivos es de ; Esto significa que si hacemos pruebas independientes en una cadena , el número esperado de éxitos es . (Tenga en cuenta que una probabilidad de falso positivo menor que conducirá a un valor esperado aún más bajo y, por lo tanto, a límites aún más estrictos en las estimaciones por venir.) Ahora, veamos la probabilidad de que tengamos más de falsos positivos (es decir , que ). Nosotros tomamos$X_i$$i$$X=\sum X_i$$.9$$n$$\sigma\notin L$$\mu = E(X) = 0.9n$$.9$$0.925n$$X\gt 0.925n$$\delta = \left(\frac{0.925}{0.9}\right)-1 =\frac{1}{36}$ ; luego y así tenemos .$\left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right) \approx.99961\lt \frac{2999}{3000}$$Pr(X\gt 0.925n)\lt\left(\frac{2999}{3000}\right)^{0.9n}$

A partir de aquí, debería quedar claro que al tomar suficientemente grande podemos reducir esta probabilidad a . Por lo tanto, para esta suficientemente grande , si aceptamos la cadena solo si el número de pruebas exitosas en es mayor que , entonces nuestra probabilidad de aceptar una cadena cae por debajo de . Tenga en cuenta que esta es constante , no depende del tamaño de nuestro problema; ya que estamos ejecutando nuestro polinomial$n$$\lt\frac{1}{3}$$n$$\sigma$$\sigma$$.925n$$\sigma\notin L$$\frac{1}{3}$$n$$BPP(0.9, 0.95)$algoritmo un número constante de veces, el tiempo total de ejecución de nuestro nuevo procedimiento sigue siendo polinomial. Un análisis similar en la otra dirección mostrará que la probabilidad de un 'falso negativo' (que para una cadena que está en nuestro idioma) estará acotada por para alguna , y así nuevamente podemos tomar suficientemente grande como para limitar la probabilidad de un falso negativo por (o, en otras palabras, para garantizar al menos probabilidad de aceptar en una cadena ) Esto muestra que$X\lt.925n$$c^n$$c$$n$$\frac{1}{3}$$\frac{2}{3}$$\sigma\in L$$BPP(.9, .95)\subseteq BPP(\frac13, \frac23) \equiv BPP$, y el comentario de Yuval muestra cómo probar la equivalencia inversa a través de un procedimiento similar.

Canonicamente, esto se conoce como amplificación de probabilidad y es un método inmensamente útil para tratar con clases probabilísticas. Las constantes específicas son menos importantes, obviamente, entonces el hecho de que el límite de Chernoff nos permite vincular nuestras probabilidades de 'resultado falso' por alguna función exponencial del número de ensayos, por lo que pueden hacerse arbitrariamente pequeños con solo un número modesto de ensayos.