Comprensión concreta de la diferencia entre las definiciones PP y BPP

9

Estoy confundido acerca de cómo se definen PP y BPP . Supongamos que es la función característica de un lenguaje . M ser la máquina probabilística de Turing. ¿Son correctas las siguientes definiciones: $\chi$ $\mathcal{L}$
$BPP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] \geq \frac{1}{2} + \epsilon \quad \forall x \in \mathcal{L},\ \epsilon > 0 \}$
$PP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] > \frac{1}{2} \}$

Si la definición es incorrecta, intente hacer un cambio mínimo para corregirla (es decir, no proporcione otra definición equivalente que use máquina de conteo o algún modelo modificado). No puedo distinguir adecuadamente las condiciones de probabilidad en ambas definiciones.

Algunos ejemplos concretos con una visión clara de los puntos sutiles serían muy útiles.

complexity-theory terminology randomized-algorithms complexity-classes DurgaDatta
fuente

10

Eso me parece correcto. La diferencia entre BPP y PP es que para BPP la probabilidad tiene que ser mayor que $1/2$ por una constante , mientras que para PP que podría ser $1/2+ 1/2^n$ . Por lo tanto, para problemas de BPP, puede hacer amplificación de probabilidad con un pequeño número de repeticiones, mientras que para problemas generales de PP no puede.

adrianN
fuente

12

La respuesta de Vor da la definición estándar. Permítanme tratar de explicar la diferencia un poco más intuitivamente.

Sea un algoritmo de tiempo polinomial probabilístico de error acotado para un lenguaje que responde correctamente con probabilidad al menos $M$ $L$ . Seala entradael tamaño de la entrada. $p\geq\frac{1}{2}+\delta$ $x$ $n$

Lo que distingue a un arbitrario algoritmo de un algoritmo es la brecha positiva entre la probabilidad de aceptar y la probabilidad de aceptar . $\mathsf{PP}$ $\mathsf{BPP}$ $x\in L$ $x\notin L$ Lo esencial de es que la brecha es al menos . Trataré de explicar por qué esta distinción es significativa y nos permite considerar que se considere algoritmos eficientes (incluso se conjetura que es igual a $\mathsf{BPP}$ $n^{-O(1)}$ $\mathsf{BPP}$ $\mathsf{P}$ ) mientras que se considera ineficiente (en realidad, contiene ). Todo esto proviene de esta brecha. $\mathsf{PP}$ $\mathsf{PP}$ $\mathsf{NP}$

Comencemos mirando más cuidadosamente. $\mathsf{PP}$

Tenga en cuenta que si un algoritmo usa a lo sumo bits aleatorios durante su ejecución y la probabilidad de error es menor que entonces la probabilidad de error es en realidad , no puede haber ninguna elección de bits aleatorios que hagan que el algoritmo Responde incorrectamente. $r(n)$ $2^{-r(n)}$ $0$

Además, un algoritmo con tiempo de ejecución no puede usar más de bits aleatorios, por lo que si el error de un algoritmo probabilístico con el peor tiempo de ejecución es mejor que $t(n)$ $t(n)$ $t(n)$

Con un argumento similar, podemos mostrar que el caso en el que la diferencia entre la probabilidad de aceptar una y la probabilidad de aceptar una es demasiado pequeña es similar al caso en el que casi no tenemos diferencia como en caso. $x\in L$ $x\notin L$ $\mathsf{PP}$

Ahora vamos a avanzar hacia . $\mathsf{BPP}$

En algoritmos probabilísticos, podemos aumentar la probabilidad de responder correctamente. Digamos que queremos aumentar la probabilidad de corrección a para decir probabilidad de error (error exponencialmente pequeño). $1-\epsilon$ $\epsilon=2^{-n}$

La idea es simple: ejecuta varias veces y toma la respuesta de la mayoría. $M$

¿Cuántas veces debemos ejecutar para obtener la probabilidad de error como máximo ? veces. La prueba se da al final de esta respuesta. $M$ $\epsilon$ $\Theta(\delta^{-1} \lg \epsilon)$

Ahora tomemos en consideración que los algoritmos que estamos discutiendo deben ser de tiempo polinómico. Eso significa que no podemos ejecutar más de polinomio muchas veces. En otras palabras, , o más simplemente $M$ $\Theta(\delta^{-1} \ln \epsilon) = n^{O(1)}$

δ^{- 1} \lg ϵ = {norte}^{O (1)}

$\delta^{-1} \lg \epsilon = n^{O(1)}$

Esta relación clasifica los algoritmos probabilísticos de error acotado en clases según su probabilidad de error. No hay ninguna diferencia entre la probabilidad de error siendo ser o una constante positiva (es decir, no cambia con ) o $\epsilon$ $2^{-n}$ $n$ . Podemos pasar de uno de estos a los otros mientras permanecemos dentro del tiempo polinómico. $\frac{1}{2}-n^{O(1)}$

Sin embargo, si es demasiado pequeño, por ejemplo , , o incluso entonces no tenemos una forma de aumentar la probabilidad de corrección y la reducción de la probabilidad de error suficientemente para entrar en . $\delta$ $0$ $2^{-n}$ $n^{-\omega(1)}$ $\mathsf{BPP}$

El punto principal aquí es que en podemos reducir eficientemente la probabilidad de error exponencialmente, por lo que estamos casi seguros de las respuestas y eso es lo que nos hace considerar esta clase de algoritmos como algoritmos eficientes. La probabilidad de error puede reducirse tanto que es más probable una falla de hardware o incluso un meteorito que cae sobre la computadora es más probable que cometer un error por el algoritmo probabilístico. $\mathsf{BPP}$

Eso no es cierto para , no conocemos ninguna forma de reducir la probabilidad de error y nos quedamos casi como si estuviéramos respondiendo lanzando una moneda para obtener la respuesta (no estamos completamente, las probabilidades no son la mitad y mitad, pero está muy cerca de esa situación). $\mathsf{PP}$

Esta sección da la prueba de que para obtener la probabilidad de error cuando comenzamos con un algoritmo con gap $\epsilon$ debemos ejecutarveces. $(\frac{1}{2}-\delta,\frac{1}{2}+\delta)$ $M$ $\Theta(\delta^{-1} \lg \epsilon)$

Sea el algoritmo que ejecuta por veces y luego responde de acuerdo con la respuesta de la mayoría. Por simplicidad, supongamos que es impar, por lo que no tenemos vínculos. $N_k$ $M$ $k$ $k$

Considere el caso de que . El caso es similar. Entonces $x \in L$ $x \notin L$ Para analizar la probabilidad de corrección denecesitamos estimar la probabilidad de que la mayoría de lascorridas acepten.

PAGS r {METRO (X) acepta} = pags \geq \frac{1}{2} + δ

$\mathsf{Pr}\{M(x) \text{ accepts}\} = p \geq \frac{1}{2} + \delta$

N_{k}

$N_k$

k

$k$

Sea 1 si la ejecución th acepta y si rechaza. Tenga en cuenta que cada ejecución es independiente de las demás, ya que utilizan bits aleatorios independientes. Por lo tanto, s son variables aleatorias booleanas independientes donde $X_i$ $i$ $0$ $X_i$

mi [X_{yo}] = PAGS r {X_{yo} = 1} = PAGS r {METRO (X) acepta} = pags \geq \frac{1}{2} + δ

$\mathbb{E}[X_i] = \mathsf{Pr}\{X_i=1\} = \mathsf{Pr}\{M(x)\text{ accepts}\} = p \geq \frac{1}{2}+\delta$

Sea . Necesitamos estimar la probabilidad de que la mayoría acepte, es decir, la probabilidad de que $Y = \Sigma_{i=1}^k X_i$ . $Y\geq\frac{k}{2}$

PAGS r {{norte}_{k} (X) acepta} = PAGS r {Y \geq \frac{k}{2}}

$\mathsf{Pr}\{N_k(x) \text{ accepts}\} = \mathsf{Pr}\{Y \geq \frac{k}{2}\}$

¿Cómo hacerlo? Podemos usar el límite de Chernoff que nos dice la concentración de probabilidad cerca del valor esperado. Para cualquier variable aleatoria con valor esperado , tenemos $Z$ $\mu$

PAGS r {El | Z - μ El | > α μ} < {mi}^{\frac{α^{2}}{4 4} μ}

$\mathsf{Pr}\{|Z-\mu| > \alpha\mu\} < e^{\frac{\alpha^2}{4}\mu}$

lo que dice que la probabilidad de que sea lejos de su valor esperado disminuye exponencialmente a medida que aumenta. Lo usaremos para limitar la probabilidad de $Z$ $\alpha\mu$ $\mu$ $\alpha$ . $Y < \frac{k}{2}$

mi [Y] = mi [Σ_{yo = 1}^{k} X_{yo}] = Σ_{yo = 1}^{k} mi [X_{yo}] = k pags \geq \frac{k}{2} + k δ

$\mathbb{E}[Y] = \mathbb{E}[\Sigma_{i=1}^k X_i] = \Sigma_{i=1}^k \mathbb{E}[X_i] = kp \geq \frac{k}{2} + k\delta$

$Y< \frac{k}{2}$ $|Y-(\frac{k}{2}+k\delta)| > k\delta$

PAGS r {El | Y - k pags El | > α k pags} < {mi}^{- \frac{α^{2}}{4 4} k pags}

$Pr\{|Y - kp| > \alpha kp\} < e^{-\frac{\alpha^2}{4}kp}$

$\alpha$ $\alpha kp = k\delta$ $\alpha = \frac{\delta}{p} \leq \frac{2\delta}{2\delta+1}$

Por lo tanto tenemos

PAGS r {Y < \frac{k}{2}} \leq PAGS r {El | Y - (\frac{k}{2} + k δ) El | > k δ} \leq PAGS r {El | Y - k pags El | > α k pags} < {mi}^{- \frac{α^{2}}{4 4} k pags}

$Pr\{Y < \frac{k}{2} \} \leq Pr\{|Y - (\frac{k}{2}+k\delta)| > k\delta\} \leq Pr\{|Y - kp| > \alpha kp\} < e^{-\frac{\alpha^2}{4}kp}$

y si haces los cálculos verás que

\frac{α^{2}}{4 4} k pags \leq \frac{δ^{2}}{4 4 δ + 2} k = Θ (k δ)

$\frac{\alpha^2}{4}kp \leq \frac{\delta^2}{4\delta+2}k = \Theta(k\delta)$

tenemos

PAGS r {Y < \frac{k}{2}} < {mi}^{- Θ (k δ)}

$Pr\{Y < \frac{k}{2} \} < e^{-\Theta(k\delta)}$

$\epsilon$

{mi}^{- Θ (k δ)} \leq ϵ

$e^{-\Theta(k\delta)} \leq \epsilon$

o en otras palabras

Θ (δ^{- 1} \lg ϵ) \leq k

$\Theta(\delta^{-1} \lg \epsilon) \leq k$

$N_k$ $k$ $M$

$\frac{1}{2}$

Kaveh
fuente

7

Usando su notación:

$BPP =\{L : \exists$ $M,$ $0 < c \leq 1/2$ $\forall x \; Pr[\chi_L(x) = M(x)] \geq \frac{1}{2} + c\}$

$PP =\{L : \exists$ $M$ $\forall x \; Pr[\chi_L(x) = M(x)] > \frac{1}{2}\}$

AdrianN ha señalado la diferencia, y también puede echar un vistazo a Wikipedia PP vs BPP

Vor
fuente

Comprensión concreta de la diferencia entre las definiciones PP y BPP

Respuestas: