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:LχL
P P = { L : P r [ χ ( x ) M ( x ) ] > 1BPP={L:Pr[χ(x)M(x)]12+ϵxL, ϵ>0}
PAGSPAGS={L:PAGSr[χ(X)METRO(X)]>12}

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.

DurgaDatta
fuente

Respuestas:

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/2norte . 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 L que responde correctamente con probabilidad al menos p 1METROL. Seaxla entradaynel tamaño de la entrada.pags12+δXnorte

Lo que distingue a un arbitrario algoritmo de un B P P algoritmo es la brecha positiva entre la probabilidad de aceptar x L y la probabilidad de aceptar x L . PAGSPAGSsiPAGSPAGSXLXLLo esencial de es que la brecha es al menos n - O ( 1 ) . Trataré de explicar por qué esta distinción es significativa y nos permite considerar que B P P se considere algoritmos eficientes (incluso se conjetura que es igual a PsiPAGSPAGSnorte-O(1)siPAGSPAGSPAGS) mientras que se considera ineficiente (en realidad, P P contiene N P ). Todo esto proviene de esta brecha.PAGSPAGSPAGSPAGSnortePAGS

Comencemos mirando más cuidadosamente.PAGSPAGS

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 2 - r ( n ), entonces la probabilidad de error es en realidad 0 , no puede haber ninguna elección de bits aleatorios que hagan que el algoritmo Responde incorrectamente.r(norte)2-r(norte)0 0

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

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 x L es demasiado pequeña es similar al caso en el que casi no tenemos diferencia como en P P caso.XLXLPAGSPAGS

Ahora vamos a avanzar hacia .siPAGSPAGS

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 ϵ = 2 - n (error exponencialmente pequeño).1-ϵϵ=2-norte

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

¿Cuántas veces debemos ejecutar para obtener la probabilidad de error como máximo ϵ ? Θ ( δ - 1 lg ϵ ) veces. La prueba se da al final de esta respuesta.METROϵΘ(δ-1lgϵ)

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, Θ ( δ - 1 ln ϵ ) = n O ( 1 ) , o más simplementeMETROΘ(δ-1Enϵ)=norteO(1)

δ-1lgϵ=norteO(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 2 - n o una constante positiva (es decir, no cambia con n ) o 1ϵ2-nortenorte. Podemos pasar de uno de estos a los otros mientras permanecemos dentro del tiempo polinómico.12-norteO(1)

Sin embargo, si es demasiado pequeño, por ejemplo 0 , 2 - n , o incluso n - ω ( 1 ) 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 B P P .δ0 02-nortenorte-ω(1)siPAGSPAGS

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.siPAGSPAGS

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).PAGSPAGS


Esta sección da la prueba de que para obtener la probabilidad de error cuando comenzamos con un algoritmo con gap ( 1ϵdebemos ejecutarMΘ(δ-1lgϵ)veces.(12-δ,12+δ)METRO Θ(δ-1lgϵ)

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

Considere el caso de que . El caso x L es similar. Entonces P r { M ( x )  acepta } = p 1XLXL Para analizar la probabilidad de corrección deNknecesitamos estimar la probabilidad de que la mayoría de laskcorridas acepten.

PAGSr{METRO(X) acepta}=pags12+δ
nortekk

Sea 1 si la ejecución i th acepta y 0 si rechaza. Tenga en cuenta que cada ejecución es independiente de las demás, ya que utilizan bits aleatorios independientes. Por lo tanto, X i s son variables aleatorias booleanas independientes donde E [ X i ] = P r { X i = 1 } = P r { M ( x )  acepta } = p 1Xyoyo0 0Xyo

mi[Xyo]=PAGSr{Xyo=1}=PAGSr{METRO(X) acepta}=pags12+δ

Sea . Necesitamos estimar la probabilidad de que la mayoría acepte, es decir, la probabilidad de que Y kY=Σyo=1kXyo .Yk2

PAGSr{nortek(X) acepta}=PAGSr{Yk2}

¿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 μ , tenemosZμ

PAGSr{El |Z-μEl |>αμ}<miα24 4μ

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 Y < kZαμμα .Y<k2

mi[Y]=mi[Σyo=1kXyo]=Σyo=1kmi[Xyo]=kpagsk2+kδ

Y<k2El |Y-(k2+kδ)El |>kδ

PAGSr{El |Y-kpagsEl |>αkpags}<mi-α24 4kpags

ααkpags=kδα=δpags2δ2δ+1

Por lo tanto tenemos

PAGSr{Y<k2}PAGSr{El |Y-(k2+kδ)El |>kδ}PAGSr{El |Y-kpagsEl |>αkpags}<mi-α24 4kpags

y si haces los cálculos verás que

α24 4kpagsδ24 4δ+2k=Θ(kδ)

tenemos

PAGSr{Y<k2}<mi-Θ(kδ)

ϵ

mi-Θ(kδ)ϵ

o en otras palabras

Θ(δ-1lgϵ)k

nortekkMETRO

12

Kaveh
fuente
7

Usando su notación:

siPAGSPAGS={L:METRO,0 0<C1/ /2XPAGSr[χL(X)=METRO(X)]12+C}

PAGSPAGS={L:METROXPAGSr[χL(X)=METRO(X)]>12}

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

Vor
fuente