Quando o BPP com uma moeda tendenciosa é igual ao BPP padrão?

10

Permita que uma máquina de Turing probabilística tenha acesso a uma moeda injusta que aparece cara com probabilidade (os flips são independentes). Defina como a classe de idiomas reconhecíveis por essa máquina no tempo polinomial. É um exercício padrão para provar que:pBPPp

A) Se é racional ou mesmo B P P -computable então B P P p = B P P . (Por B P P -computable eu média: existe um algoritmo polinomial que está sendo alimentado ao acaso n em retornos unárias whp o racionais binário com denominador 2 n que se encontra dentro de 2 - n - 1 de p .)pBPPBPPp=BPPBPPn2n2n1p

B) Para alguns uncomputable a classe B P P P contém uma linguagem indecidible e, portanto, é maior do que B P P . Tais valores de p formam um conjunto denso em ( 0 , 1 ) .pBPPpBPPp(0,1)

Minha pergunta é a seguinte: o que acontece no meio? Existe um critério para ? Em particular:BPPp=BPP

1) Existem probabilidades incomputáveis ​​em p de tal modo que B P P p = B P P ? (Eles podem ser computados em algumas classes mais altas).BPPpBPPp=BPP

2) mais largo que B P P para todos os p não- computáveis ? (Os parâmetros em questão são aqueles cuja expansão binária contém seqüências muito longas de zeros e / ou uns. Nesse caso, a computação de bits por amostragem aleatória pode levar um tempo muito longo e até incômodo, e o problema não pode ser redimensionado para o tempo polinomial. Às vezes, o dificuldade pode ser superada por outra base de expansão, mas certos p podem enganar todas as bases).BPPpBPPpp

Daniil Musatov
fonte
O que exatamente você quer dizer com p ser (in) computável?
Daniello
Eu adicionei a definição de -computable. Para computável em geral, pode-se simplesmente soltar as palavras "polinômio aleatório" ou simplesmente dizer que a expansão binária é computável. (Com recursos limitados isso não é o mesmo.)BPP
Daniil Musatov
Penso que para cada p não computável, porque dada uma moeda com viés de p, pode-se calcular o n- ésimo bit de p por amostragem. Suponha que possamos calcular o n- ésimo bit no tempo f ( n ) , então o idioma que contém 1 x para todos os x, de modo que o f - 1 ( x ) 'o bit de p seja 1 esteja em B P P pBPPpBPPppnpnf(n)1xxf1(x)p1BPPp, mas claramente é incontestável.
Daniello
Definitivamente, isso é verdade para a grande maioria das . Mas há uma ressalva: se p contiver sequências muito longas de zeros e uns, pode ser necessária uma amostragem muito longa para determinar o n- ésimo bit. Essa amostragem pode ser tão longa que f ( n ) seria incontestável (como a função Busy Beavers). Também duvido que possa ser calculado com precisão a partir da própria amostragem. E parece que sem computar f ( n ) não se pode reconhecer a linguagem mencionada. ppnf(n)f(n)
Daniil Musatov

Respostas:

1

1) Sim, mas apenas por causa da sua definição. Pegue uma linguagem unária (sim, eu sei que isso pode estar vazio, nesse caso, basta pegar algo ainda maior que E X P ), que é muito escasso no sentido de que n L se n não é uma torre de 2 ' s , ou seja, da forma 2 2 2 . Defina p = n L 1 / n . Este p não é BLEXPBPPEXPnLn2s222p=nL1/np -computable, mas p pode ser aproximada em P -se a um erro aditivo suficientemente pequena que permite a simulação de um B P P p máquina.BPPpPBPPp

Se você tivesse definido -computable de tal forma que você quiser aproximada p -se a um erro aditivo de 1 / n (em vez de 1 / 2 n ) em tempo polinomial, as coisas seriam diferentes.BPPp1/n1/2n

Atualizar. A resposta abaixo é para o caso em que o erro aditivo que permitimos é vez de 2 - n - 1 .2n2n1

2) Sim, porque aqui você pode esquecer a restrição polinomial das classes e, amostrando vezes, pode obter o n- ésimo bit de p em B P P p .2nnpBPPp

domotorp
fonte
2) Penso que o teorema do limite central sugere que se deve amostrar , e não 2 n , vezes para obter a precisão 2 - n . Mas o principal problema é que, às vezes, precisamos de uma precisão muito maior. Diga se | p - 122n2n2nentão é preciso1|p12|<ϵ amostras para calcular ainda o primeiro dígito. E o número de amostras necessárias pode ser arbitrariamente, mesmo que de maneira incontestável, grande. O ponto é um pouco esclarecido na edição. 1ϵ2
Daniil Musatov 08/08/16
@ Daniil: Como já comentei a questão, você não pediu o cálculo dos dígitos em sua definição de -computável. Portanto, se p é igual a, digamos, 0,01111111111 , deve-se adivinhar 1 para o primeiro dígito após a vírgula, de acordo com a sua definição. BPPp0.011111111111
domotorp 8/08/16
Agora estamos falando de desconectável , não estamos? Se eu entendi direito, você sugere não calcular amostrando dígitos de p , mas sim calcular se o i- ésimo dígito da aproximação racional binária 2 - i - 1 de p é 1. Mas aqui enfrentamos o mesmo problema: calcular o primeiro dígito, precisamos distinguir 0,010000000001 e 0,001111111110. ppi2i1p
Daniil Musatov
@ Daniil: OK, meu mal, eu pensei que você queria um racional binário cuja distância é no máximo da p . Atualizei minha resposta de acordo. Você está feliz com a minha solução para 1)? 2np
Domotorp 8/08