Prove ou refute: BPP (0.90,0.95) = BPP

Eu realmente gostaria da sua ajuda para provar ou refutar a seguinte reivindicação: . Na teoria da complexidade computacional, BPP, que significa tempo polinomial probabilístico de erro limitado é a classe de problemas de decisão solucionáveis ​​por uma máquina de Turing probabilística em tempo polinomial, com uma probabilidade de erro de no máximo para todas as instâncias . .$BPP(0.90,0.95)=BPP$$\frac{1}{3}$$BPP=BPP(\frac{1}{3},\frac{2}{3})$

Não é imediato que qualquer um dos conjuntos seja um subconjunto do outro, pois se a probabilidade de erro for menor que ela não precisará ser menor que e se for maior que não precisa ser maior que .$0.9$$\frac{1}{3}$$\frac{2}{3}$$0.905$

Estou tentando usar a desigualdade de Chernoff para provar a afirmação, não sei exatamente como. Eu realmente gostaria da sua ajuda. Existe uma afirmação geral sobre essas relações que eu possa usar?

Para expandir meu comentário em uma resposta: a forma multiplicativa do limite de Chernoff diz que se a expectativa para a soma de variáveis ​​binárias aleatórias independentes é , então a probabilidade de se perder ' muito longe 'dessa expectativa é: .$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$

Agora, imagine um procedimento em que, dada uma string para testar, executamos tentativas de nosso algoritmo (para que alguns sejam escolhidos posteriormente) e aceitamos se pelo menos dessas tentativas aceitam . Podemos usar o limite de Chernoff para encontrar a probabilidade de falha em termos de seguinte maneira:$\sigma$$n$$BPP(0.90, 0.95)$$n$$0.925n$$\sigma$$n$

Let denotam o resultado do th julgamento, e assim o número de tentativas bem-sucedidas. Podemos assumir de maneira conservadora que nossa probabilidade de falsos positivos é ; isso significa que, se fizermos tentativas independentes em uma string , o número esperado de sucessos será . (Observe que uma probabilidade de falso positivo menor que levará a um valor esperado ainda mais baixo e, portanto, a limites ainda mais apertados nas estimativas futuras.) Agora, vejamos a probabilidade de termos mais de falsos positivos (ou seja, , que ). Nós levamos$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}$ ; então e, portanto, temos .$\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 daqui, deve ficar claro que, tomando suficientemente grandes, podemos reduzir essa probabilidade para . Portanto, para esse suficientemente grande , se aceitarmos a string apenas se o número de tentativas bem-sucedidas em for maior que , nossa probabilidade de aceitar uma string cairá abaixo de . Observe que este é constante , não depende do tamanho do nosso problema; já que estamos executando nosso polinomial$n$$\lt\frac{1}{3}$$n$$\sigma$$\sigma$$.925n$$\sigma\notin L$$\frac{1}{3}$$n$$BPP(0.9, 0.95)$algoritmo um número constante de vezes, o tempo total de execução do nosso novo procedimento ainda é polinomial. Uma análise semelhante indo na outra direção mostrará que a probabilidade de um 'falso negativo' (que para uma string que está em nossa linguagem) será limitada por para alguns , e, novamente, podemos tome grande o suficiente para limitar a probabilidade de um falso negativo por (ou, em outras palavras, para garantir pelo menos probabilidade de aceitar em uma string ) Isso mostra 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$, e o comentário de Yuval mostra como provar a equivalência reversa por meio de um procedimento semelhante.

Canonicamente, isso é conhecido como amplificação de probabilidade e é um método imensamente útil para lidar com classes probabilísticas. As constantes específicas são menos importantes, obviamente, o fato de que o limite de Chernoff nos permite limitar nossas probabilidades de 'resultado falso' por alguma função exponencial do número de tentativas, para que elas possam ser arbitrariamente pequenas com apenas um número modesto de tentativas.