A aleatoriedade verdadeira (comprovadamente) pode ser substituída pela aleatoriedade de Kolmogorov para RP?

Houve alguma tentativa de mostrar que a aleatoriedade de Kolmogorov seria suficiente para RP ? A probabilidade usada na afirmação "Se a resposta correta for SIM, então (a máquina de Turing probabilística) retorna SIM com probabilidade ..." estará sempre bem definida nesse caso? Ou haveria apenas limites superior e inferior para essa probabilidade? Ou sempre haveria alguma máquina de Turing probabilística, para a qual as probabilidades seriam bem definidas (ou pelo menos o limite inferior que deveria ser maior que 1/2)?

A classe RP aqui é relativamente arbitrária e também se poderia fazer essa pergunta por noções mais fracas de aleatoriedade (pseudo-) do que a aleatoriedade de Kolmogorov. Mas a aleatoriedade de Kolmogorov parece ser um bom ponto de partida.

Compreender a palavra "probabilidade" seria parte de uma tentativa de mostrar que a aleatoriedade de Kolmogorov funciona para RP. No entanto, deixe-me tentar descrever uma abordagem possível, esclarecer o que isso poderia significar e por que falei sobre os limites superior e inferior:

Deixe $s$ ser um (Kolmogorov aleatório) string. Seja $A$ uma determinada máquina de Turing probabilística correspondente a um idioma do RP. Execute $A$ com $s$ como fonte para bits aleatórios $n$ vezes, continuando a consumir bits anteriormente não consumidos de $s$ um após o outro.

Para $p_n^s:=\frac{\text{#YES result in first $n$ runs of $A$ on $s$}}{n}$$p_+^s:=\limsup_{n\to\infty}p_n^s$$p_-^s:=\liminf_{n\to\infty}p_n^s$$p_+^s$$p_-^s$$s$$p_+^s=p_-^s$$s$$p_-^{s_1}=p_-^{s_2}$$s_1$$s_2$$p\geq 1/2$$p\leq p_-^s$$s$

Eu acho que a pergunta que está sendo feita aqui é mais ou menos " existe um sentido no qual podemos substituir a sequência de bits aleatórios em um algoritmo por bits desenhados deterministicamente a partir de uma seqüência aleatória de Kolmogorov apropriadamente longa? " Essa é pelo menos a pergunta que tentarei responda! (A resposta curta é "Sim, mas somente se você amplificar a probabilidade de erro primeiro")

Sim...

Certamente podemos dizer algo aqui. Seja uma linguagem e seja um algoritmo que tome como entrada e uma sequência aleatória (a distribuição uniforme sobre ) st . Em outras palavras, é um algoritmo que erra com probabilidade no máximo .$L$$A$$x$$r\in U_{f(|x|)}$$\{0,1\}^{f(|x|)}$$\Pr[A(x,r)=L(x)]>1-\epsilon(x)$$A$$\epsilon(\cdot)$

Observe agora que, se fornece a resposta errada em , ou seja, , isso nos fornece alguns meios de descrever , em particular, podemos descrevê-la como -th string que faz com que erre emPara fazer isso, simplesmente criamos a máquina que possui , , um bit , e simplesmente enumera as opções de de até encontrar a ésima escolha de modo que .$A$$(x,r)$$A(x,r)\not=L(x)$$r$$i$$A$$x.$$x$$A$$i$$b=1\iff x\in L$$r'$$\{0,1\}^{f(|x|)}$$i$$r'$$A(x,r')\not= b$

Portanto, agora que sabemos que podemos aproveitar uma má escolha de sequência aleatória em uma descrição, vamos observar algumas condições que são suficientes para transformar nossa descrição de em uma compactação. Para descrever , precisamos de bits suficientes para descrever , , o código do nosso procedimento (o código para e a rotina que descrevemos), fornecendo como descrição o comprimento$r$$r$$x$$i$$b$$A$

Lembre-se de que é comprimento ; portanto, essa é uma compactação de se por exemplo, quando .$r$$f(|x|)$$r$

Por fim, observe que se fosse uma sequência aleatória de Kolmogorov, não teríamos essa compactação, desde que a probabilidade de erro de seja suficientemente pequena, uma sequência aleatória de Kolmogorov no lugar da sequência de bits aleatórios fará com que responda corretamente!$r$$A$$A$

Observe que a única coisa que aproveitamos em é que sua probabilidade de erro é pequena. Não nos importamos se tiver um tempo de execução extremamente longo ou se tiver um ou dois erros.$A$$A$$A$

Trazendo isso de volta à questão de (ou ou ), isso diz que, desde que amplifiquemos a probabilidade de erro de nossos algoritmos, podemos usar cadeias aleatórias de Kolmogorov no lugar de seus bits aleatórios.$RP$$coRP$$BPP$

... Mas somente se amplificarmos primeiro.

Uma pergunta de acompanhamento pode ser "posso fazer isso sem ampliar a probabilidade de erro?" Considere o seguinte algoritmo que decide e tem probabilidade de erro .$A$$\{0,1\}^*$$1/2^n$

Na entrada :$x$

• Gere uma string$r\in\{0,1\}^n$
• Se , rejeite.$r=x$
• Aceitar.

Observe que, para cada escolha de , existe alguma opção de modo que erra em , ou seja, a escolha de que é , portanto, não podemos substituir a sequência aleatória de bits usada por por uma sequência aleatória de Kolmogorov sem amplificar é probabilidade de erro!$r$$x$$A$$x$$r$ $x$$A$

Uma observação sobre a fonte: não tenho certeza se isso é novidade, mas incluí o primeiro argumento na redação do meu exame de qualificação, que estará disponível on-line depois que eu terminar de revisá-lo.