¿En qué clase están los algoritmos aleatorios que erran con exactamente un 25% de probabilidad?

Supongamos que considero la siguiente variante de BPP, que nos permite llamar E (xact) BPP: un lenguaje está en EBPP si hay un TG polinomial aleatorio que acepta cada palabra del idioma con exactamente 3/4 de probabilidad y cada palabra no en el lenguaje con exactamente 1/4 de probabilidad. Obviamente, EBPP está contenido en BPP, pero ¿son iguales? ¿Se ha estudiado esto? ¿Qué pasa con el ERP igualmente definible?

Motivación. Mi principal motivación es que quería saber cuál es el análogo teórico de la complejidad del algoritmo aleatorio `` correcto en el valor esperado '' de Faenza et al. (ver http://arxiv.org/abs/1105.4127 ) sería. Primero, quería entender qué problemas de decisión puede resolver un algoritmo de este tipo (con el peor tiempo de ejecución polinomial). Denotemos esta clase por E (esperado) V (alue) PP. Es fácil ver que USAT $\in$ EVPP. También es fácil ver que EBPP $\subset$ EVPP. Entonces esta fue mi motivación. Cualquier comentario sobre EVPP también es bienvenido.

De hecho, su algoritmo siempre genera un número no negativo. Si denotamos los problemas de decisión reconocibles por dicho algoritmo por EVP (ositivo) PP, entonces todavía tenemos USAT $\in$ EVPPP. Si bien EBPP podría no ser un subconjunto de EVPPP, tenemos ERP $\subset$ EVPPP. Tal vez utilizando estos podamos definir un rango (no negativo) para problemas de decisión.

En una nota al margen, no está claro que EBPP sea una clase robusta. Por ejemplo, si en lugar de permitir que el algoritmo arroje una moneda imparcial, si se le dio una moneda imparcial de 3 caras o un dado de 6 caras, no está claro que obtenga la misma clase. BPP sigue siendo el mismo si cambia estos detalles.

De todos modos, su pregunta principal es si EBPP es igual a BPP o no. Me parece que EBPP está más cerca de P que de BPP. Considere la complejidad de la consulta o la versión de Oracle de estas clases donde tienen acceso a una cadena de entrada grande y tienen que hacer consultas para aprender los bits de esta cadena. Si usted tiene un algoritmo que calcula P una función con Q consultas, entonces existe una exacta representación de polinomio de grado Q de f sobre R . (Este es el argumento habitual del método polinomial). Por otro lado, si tiene un algoritmo BPP, obtiene un polinomio de grado Q sobre R que se aproxima a $f$$Q$$Q$$f$$\mathbb{R}$$Q$$\mathbb{R}$$f$en el sentido de que su valor es cercano al valor de en cada entrada.$f$

Dado un algoritmo EBPP para una función , podemos construir un polinomio que genera 1/4 cuando la respuesta es NO y 3/4 cuando la respuesta es SÍ. Al restar 1/2 y multiplicar por 2, puede obtener un polinomio que representa exactamente, como en el caso de P. Esto me sugiere que EBPP está más cerca de P.$f$

Esta observación también se puede utilizar para mostrar una separación de oráculo entre EBPP y BPP. Considere el problema de la promesa de mayoría, en el que se le promete que la entrada tiene más de 2N / 3 1s o menos de N / 3 1s y debe decidir cuál es el caso. Esto está claramente en BPP. Usando el argumento polinómico descrito anteriormente, se puede demostrar que esta función requiere consultas para una máquina EBPP. Pero tenga en cuenta que también puede probar una separación de oráculo a la inversa, entre P y EBPP. ¿Entonces quizás los resultados del oráculo no dicen mucho sobre este problema? O tal vez lo que dicen es que será difícil mostrar igualdad en cualquier dirección.$\Omega(N)$

Con respecto a las separaciones de oráculos, hay un oráculo con EBPP = BPP = EXP ^NP , y un oráculo con P = ⊕P (y, por lo tanto, EBPP = P) y BPP = EXP ^NP .

Una construcción del oráculo BPP = EXP ^NP (incluido el del artículo de Wikipedia de BPP ) es elegir un ^problema completo de EXP ^NP relativizado y proceder recursivamente sobre el tamaño de entrada (para ese problema), corregir los resultados para instancias de problemas de ese tamaño, y luego proporcione respuestas a ese problema si se le consulta con la entrada y un relleno (de la longitud adecuada) que no se ha solucionado. Para EBPP = EXP ^NP , en lugar de dar casi siempre las respuestas correctas, podemos dar suficientes respuestas incorrectas para que los recuentos sean exactamente correctos. También hay un oráculo en el que el análogo de error cero de EBPP (exactamente 1/2 probabilidad de error de informe) es igual a EXP (y un oráculo con P = ⊕P pero ZPP = EXP).

Aquí se observa el oráculo P = ⊕P y BPP = EXP ^NP .

Además de estar en BPP y en C ₌ P, EBPP está en ⊕P ya que podemos reducir la probabilidad al número de testigos y luego ajustar ese número.

En el mundo no relativizado, BPP probablemente es igual a P, pero la evidencia es aún más fuerte para EBPP. EBPP depende del número exacto de rutas de una manera que, a menos que se mantenga una cancelación inesperada, parece esencialmente imposible de aprovechar.

Esta es una respuesta parcial; tal vez inspire a alguien más a proporcionar una mejor. $\newcommand{\EBPP}{\mathsf{EBPP}}$ $\newcommand{\CP}{\mathsf{C}_=\mathsf{P}}$

Su clase es un caso especial de C = P . Creo que una forma de definir C = P es la siguiente (consulte la Sección 2 de este documento ). Un lenguaje L está en C = P si hay un verificador de tiempo polinomial V tal que$\EBPP$$\CP$$\CP$$L$$\CP$$V$

• si está en L , entonces Pr w [ V ( x , w )  acepta ] = $x$$L$ y$\Pr_w[V(x, w) \text{ accepts}] = \frac{3}{4}$
• si no está en L , entonces Pr w [ V ( x , w )  acepta ] ≠ $x$$L$ .$\Pr_w[V(x, w) \text{ accepts}] \neq \frac{3}{4}$

(La probabilidad de completitud puede ser esencialmente cualquier fracción fija; elegí para que coincida con la probabilidad dada en su pregunta.)$\frac{3}{4}$

Una forma de definir es la siguiente. Un lenguaje L está en E B P P si hay un verificador de tiempo polinomial V tal que$\EBPP$$L$$\EBPP$$V$

• si está en L , entonces Pr w [ V ( x , w )  acepta ] = $x$$L$ y$\Pr_w[V(x, w) \text{ accepts}] = \frac{3}{4}$
• si no está en L , entonces Pr w [ V ( x , w )  acepta ] = $x$$L$ .$\Pr_w[V(x, w) \text{ accepts}] = \frac{1}{4}$