Le vrai hasard peut-il (vraisemblablement) être remplacé par le hasard de Kolmogorov pour RP?

Y a-t-il eu des tentatives pour montrer que le caractère aléatoire de Kolmogorov serait suffisant pour RP ? La probabilité utilisée dans l'énoncé "Si la bonne réponse est OUI, alors elle (la machine probabiliste de Turing) renvoie OUI avec probabilité ..." serait-elle toujours bien définie dans ce cas? Ou y aurait-il seulement des limites supérieures et inférieures pour cette probabilité? Ou y aurait-il seulement toujours une machine de Turing probabiliste, pour laquelle les probabilités seraient bien définies (ou au moins la borne inférieure qui devrait être supérieure à 1/2)?

La classe RP ici est relativement arbitraire, et on pourrait également poser cette question pour des notions plus faibles de (pseudo-) hasard que le hasard de Kolmogorov. Mais le caractère aléatoire de Kolmogorov semble être un bon point de départ.

Donner un sens au mot "probabilité" ferait partie d'une tentative de montrer que le caractère aléatoire de Kolmogorov fonctionne pour RP. Cependant, permettez-moi d'essayer de décrire une approche possible, de clarifier ce qu'elle pourrait signifier et pourquoi j'ai parlé des limites supérieures et inférieures:

Soit une chaîne (aléatoire de Kolmogorov). Soit A une machine de Turing probabiliste donnée correspondant à un langage de RP. Exécutez A avec s comme source pour les bits aléatoires n fois, en continuant à consommer les bits précédemment non consommés de s l' un après l'autre.$s$$A$$A$$s$$n$$s$

Pour , soitp s + :=lim supn→∞p s n etp s - :=lim infn→∞p s n . Remarquez quep s + etp s - sont bien définis pour une chaîne données, même si elle ne serait pas aléatoire. Mais on peut se demander sip s + =p s - dans le cas oùsest aléatoire de Kolmogorov, ou si$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$ pour deux chaînes aléatoires arbitraires de Kolmogorov s 1 et s 2 . Ou s'il existe un p ≥ une / 2 de telle sorte que p ≤ p s - pour toute chaîne aléatoire Kolmogorov s .$p_-^{s_1}=p_-^{s_2}$$s_1$$s_2$$p\geq 1/2$$p\leq p_-^s$$s$

Je pense que la question posée ici est à peu près " y a-t-il un sens dans lequel nous pouvons remplacer la séquence de bits aléatoires dans un algorithme par des bits dessinés de manière déterministe à partir d'une chaîne aléatoire de Kolmogorov suffisamment longue? " C'est au moins la question que j'essaierai de réponse! (La réponse courte est "Oui, mais seulement si vous amplifiez d'abord la probabilité d'erreur")

Oui...

$L$$A$$x$$r\in U_{f(|x|)}$$\{0,1\}^{f(|x|)}$$\Pr[A(x,r)=L(x)]>1-\epsilon(x)$$A$$\epsilon(\cdot)$

$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$

$r$$r$$x$$i$$b$$A$

$r$$f(|x|)$$r$

$r$$A$$A$

$A$$A$$A$

$RP$$coRP$$BPP$

... Mais seulement si on amplifie d'abord.

$A$$\{0,1\}^*$$1/2^n$

$x$

• $r\in\{0,1\}^n$
• $r=x$
• J'accepte.

$r$$x$$A$$x$$r$ $x$$A$

Une note sur la source: je ne sais pas si tout cela est nouveau, mais j'ai inclus le premier argument dans mon article pour mon examen de qualification qui sera finalement disponible en ligne après avoir fini de le réviser.