Compreensão concreta da diferença entre definições de PP e BPP

9

Estou confuso sobre como PP e BPP são definidos. Vamos supor χ é a função característica de uma linguagem L . M ser a máquina de Turing probabilística. As definições a seguir estão corretas:
BPP={L:Pr[χ(x)M(x)]12+ϵxL, ϵ>0}
PP={L:Pr[χ(x)M(x)]>12}

Se a definição estiver incorreta, tente fazer alterações mínimas para corrigi-las (por exemplo, não forneça outra definição equivalente que use a máquina de contar ou algum modelo modificado). Não consigo distinguir adequadamente as condições de probabilidade em ambas as definições.

Alguns exemplos concretos com uma visão clara dos pontos sutis seriam muito úteis.

DurgaDatta
fonte

Respostas:

10

Isso parece correto para mim. A diferença entre BPP e do PP é que para BPP a probabilidade tem de ser maior do que por uma constante , enquanto para o PP que poderia ser 1 / 2 + 1 / 2 n . Portanto, para problemas de BPP, você pode fazer amplificação de probabilidade com um pequeno número de repetições, enquanto que para problemas gerais de PP, não é possível.1 1/2 1 1/2+1 1/2n

adrianN
fonte
12

A resposta de Vor fornece a definição padrão. Deixe-me tentar explicar a diferença um pouco mais intuitivamente.

Seja um algoritmo de tempo polinomial probabilístico de erro limitado para uma linguagem L que responda corretamente com probabilidade pelo menosMeu. Sejaxp1 12+δx a entrada o tamanho da entrada.n

O que distingue uma arbitrária algoritmo de um B P P algoritmo é a diferença positiva entre a probabilidade de aceitar x G e a probabilidade de aceitação x L . PPBPPxeuxeuO essencial de é que a diferença seja pelo menos n - O ( 1 ) . Vou tentar explicar por que essa distinção é significativa e nos permite considerar B P P como algoritmos eficientes (mesmo conjecturados como iguais a PBPPn-O(1 1)BPPP) enquanto é considerado ineficiente (na verdade, P P contém N P ). Tudo isso vem dessa lacuna.PPPPNP

Vamos começar olhando para mais cuidado.PP

Observe que, se um algoritmo usar no máximo bits aleatórios durante sua execução e a probabilidade de erro for menor que 2 - r ( n ) , a probabilidade de erro será realmente 0 , não haverá escolha de bits aleatórios que farão o algoritmo responda incorretamente.r(n)2-r(n)0 0

Além disso, um algoritmo com tempo de execução não pode usar mais que t ( n ) bits aleatórios, portanto, se o erro de um algoritmo probabilístico com pior tempo de execuçãot(n)t(n) for melhor quet(n)

Com um argumento semelhante, podemos mostrar que o caso em que a diferença entre a probabilidade de aceitar um e a probabilidade de aceitar um x L é muito pequena é semelhante ao caso em que não temos quase nenhuma diferença, como em P caso P.xeuxLPP

Vamos agora avançar para .BPP

Em algoritmos probabilísticos, podemos aumentar a probabilidade de responder corretamente. Digamos que desejamos aumentar a probabilidade de correção para para, digamos, probabilidade de erro ϵ = 2 - n (erro exponencialmente pequeno).1ϵϵ=2n

A idéia é simples: execute várias vezes e pegue a resposta da maioria.M

Quantas vezes devemos executar para obter a probabilidade de erro no máximo ϵ ? Θ ( δ - 1 lg ϵ ) vezes. A prova é dada na parte inferior desta resposta.MϵΘ(δ1lgϵ)

Agora, vamos considerar que os algoritmos que estamos discutindo precisam ter tempo polinomial. Isso significa que não podemos executar mais do que polinomialmente muitas vezes. Em outras palavras, Θ ( δ - 1 ln ϵ ) = n O ( 1 ) , ou mais simplesmenteMΘ(δ1lnϵ)=nO(1)

δ1lgϵ=nO(1)

Essa relação categoriza os algoritmos probabilísticos de erro limitado em classes, dependendo de sua probabilidade de erro. Não existe diferença entre a probabilidade de erro ser sendo 2 - n ou uma constante positiva (isto é, não muda com n ) ouϵ2nn. Podemos passar de um desses para os outros enquanto permanecemos dentro do tempo polinomial.12nO(1)

No entanto, se é muito pequeno, digamos, 0 , 2 - n , ou mesmo n - ω ( 1 ) , então não temos uma maneira de aumentar a probabilidade de correção e reduzindo a probabilidade de erro suficientemente para entrar B P P .δ02nnω(1)BPP

O ponto principal aqui é que, em , podemos reduzir eficientemente a probabilidade de erro exponencialmente, para termos quase certeza das respostas e é isso que nos leva a considerar essa classe de algoritmos como algoritmos eficientes. A probabilidade de erro pode ser reduzida tanto que uma falha de hardware é mais provável ou até um meteoro que cai no computador é mais provável do que cometer um erro pelo algoritmo probabilístico.BPP

Isso não é verdade para , não conhecemos nenhuma maneira de reduzir a probabilidade de erro e ficamos quase como se estivéssemos respondendo jogando uma moeda para obter a resposta (não somos completamente, as probabilidades não são metade e metade, mas está muito próximo dessa situação).PP


Esta secção fornece a prova de que a obtenção de probabilidade de erro quando começamos com um algoritmo com gap ( 1ϵdevemos executarMΘ(δ-1lgϵ)vezes.(12δ,12+δ)M Θ(δ1lgϵ)

Seja o algoritmo que executa M por k vezes e depois responde de acordo com a resposta da maioria. Por uma questão de simplicidade, vamos supor que k seja ímpar para que não tenhamos laços.NkMkk

Considere o caso em que . O caso x L é semelhante. Então P r { M ( x )  aceita } = p xLxL Para analisar a probabilidade de correção deNk, precisamos estimar a probabilidade que a maioria daskexecuções aceita.

Pr{M(x) accepts}=p12+δ
Nkk

Deixe- ser 1 se o i th prazo aceita e ser 0 se ele rejeita. Observe que cada execução é independente das outras, pois elas usam bits aleatórios independentes. Assim, X i s são variáveis ​​aleatórias booleanas independentes, onde E [ X i ] = P r { X i = 1 } = P r { M ( x )  aceita } = p 1Xii0Xi

E[Xi]=Pr{Xi=1}=Pr{M(x) accepts}=p12+δ

Seja . Precisamos estimar a probabilidade que a maioria aceita, ou seja, a probabilidade de que Y kY=Σi=1kXi .Yk2

Pr{Nk(x) accepts}=Pr{Yk2}

Como fazer isso? Podemos usar o limite de Chernoff, que indica a concentração de probabilidade próxima ao valor esperado. Para qualquer variável aleatória com valor esperado μ , temosZμ

Pr{|Zμ|>αμ}<eα24μ

o que diz que a probabilidade de que esteja α µ longe do valor esperado µ diminui exponencialmente à medida que α aumenta. Vamos usá-lo para limitar a probabilidade de Y < kZαμμα .Y<k2

E[Y]=E[Σi=1kXi]=Σi=1kE[Xi]=kpk2+kδ

Y<k2|Y(k2+kδ)|>kδ que é suficiente. Nós temos

Pr{|Ykp|>αkp}<eα24kp

ααkp=kδα=δp2δ2δ+1.

Therefore we have

Pr{Y<k2}Pr{|Y(k2+kδ)|>kδ}Pr{|Ykp|>αkp}<eα24kp

and if you do the calculations you will see that

α24kpδ24δ+2k=Θ(kδ)

we have

Pr{Y<k2}<eΘ(kδ)

We want the error to be at most ϵ, so we want

eΘ(kδ)ϵ

or in other words

Θ(δ1lgϵ)k

One essential point here is that in the process we will use many more random bits and also the running time will increase, i.e. the worst-case running-time of Nk will be roughly k times the running-time of M.

Here the mid point of the gap was 12. But in general this doesn't need to be the case. We can adopt a similar method for other values by taking other fractions in place of majority for accepting.

Kaveh
fonte
7

Using your notation:

BPP={L: a probabilistic polynomial-time Turing Machine M, and a costant 0<c1/2 such that xPr[χL(x)=M(x)]12+c}

PP={L: a probabilistic polynomial-time Turing Machine M such that xPr[χL(x)=M(x)]>12}

The difference has been pointed out by adrianN, and you can also take a look at Wikipedia PP vs BPP

Vor
fonte