Kann echte Zufälligkeit (nachweislich) durch Kolmogorov-Zufälligkeit für RP ersetzt werden?

Gab es irgendwelche Versuche zu zeigen, dass Kolmogorov Zufälligkeit für RP ausreichen würde ? Wäre die Wahrscheinlichkeit, die in der Aussage "Wenn die richtige Antwort JA lautet, dann gibt sie (die probabilistische Turing-Maschine) mit Wahrscheinlichkeit JA zurück ..." in diesem Fall immer gut definiert? Oder würde es für diese Wahrscheinlichkeit nur Ober- und Untergrenzen geben? Oder würde es nur immer eine probabilistische Turing-Maschine geben, für die die Wahrscheinlichkeiten gut definiert wären (oder zumindest die Untergrenze, die größer als 1/2 sein sollte)?

Die Klasse RP ist hier relativ willkürlich, und man könnte diese Frage auch für schwächere Vorstellungen von (Pseudo-) Zufälligkeit stellen als Kolmogorov-Zufälligkeit. Aber Kolmogorov Zufälligkeit scheint ein guter Ausgangspunkt zu sein.

Das Wort "Wahrscheinlichkeit" zu verstehen, wäre Teil eines Versuchs zu zeigen, dass Kolmogorov-Zufälligkeit für RP funktioniert. Lassen Sie mich jedoch versuchen, einen möglichen Ansatz zu beschreiben, um zu klären, was dies bedeuten könnte und warum ich über Ober- und Untergrenzen gesprochen habe:

Sei $s$ eine (Kolmogorov zufällige) Zeichenfolge. Sei $A$ eine gegebene probabilistische Turingmaschine, die einer Sprache von RP entspricht. Führen Sie n- mal $A$mit $s$ als Quelle für zufällige Bits aus und verbrauchen Sie weiterhin nicht verbrauchte Bits von s nacheinander.$n$$s$

Für $p_n^s:=\frac{\text{#YES result in first $n$ runs of $A$ on $s$}}{n}$ , sei$p_+^s:=\limsup_{n\to\infty}p_n^s$und$p_-^s:=\liminf_{n\to\infty}p_n^s$. Beachten Sie, dass$p_+^s$und$p_-^s$für eine bestimmte Zeichenfolgesgut definiert sind$s$, auch wenn dies nicht zufällig wäre. Man kann sich aber fragen, ob$p_+^s=p_-^s$für den Fall, dass$s$Kolmogorov zufällig ist, oder ob$p_-^{s_1}=p_-^{s_2}$für zwei beliebige Kolmogorov-Zufallszeichenfolgen$s_1$und$s_2$. Oder ob es ein$p\geq 1/2$so dass$p\leq p_-^s$für eine beliebige Kolmogorov-Zufallszeichenfolge$s$.

Ich denke, die Frage, die hier gestellt wird, lautet ungefähr: " Gibt es einen Sinn, in dem wir die Folge von Zufallsbits in einem Algorithmus durch Bits ersetzen können, die deterministisch aus einer entsprechend langen Kolmogorov-Zufallszeichenfolge gezogen wurden? " Dies ist zumindest die Frage, die ich versuchen werde Antworten! (Die kurze Antwort lautet "Ja, aber nur, wenn Sie zuerst die Fehlerwahrscheinlichkeit erhöhen")

Ja...

Wir können hier sicherlich etwas sagen. Sei eine Sprache und sei ein Algorithmus, der als Eingabe und eine zufällige Zeichenkette (die gleichmäßige Verteilung über ) st . Mit anderen Worten, ist ein Algorithmus, der höchstens mit Wahrscheinlichkeit fehlerhaft ist .A x r ∈ U f ( | x | ) { 0 , 1 } f ( | x | ) Pr [ A ( x , r ) = L ( x ) ] > 1 - ϵ ( x ) A ϵ ( ⋅ $L$$A$$x$$r\in U_{f(|x|)}$$\{0,1\}^{f(|x|)}$$\Pr[A(x,r)=L(x)]>1-\epsilon(x)$$A$$\epsilon(\cdot)$

Beachten Sie nun, dass wenn die falsche Antwort auf dh , dies uns ein Mittel zur Beschreibung von , insbesondere können wir es als -te Zeichenfolge, die bewirkt, dass auf fehlerhaft istDazu machen wir einfach die Maschine, die , , und ein Bit fest codiert hat , und einfach die Auswahl von aus bis es die te Wahl von so dass .( x , r ) A ( x , r ) ≤ L ( x ) r i A x . x A i b = $A$$(x,r)$$A(x,r)\not=L(x)$$r$$i$$A$$x.$$x$$A$$i$r ' { 0 , 1 } f ( | x | ) i r ' A ( x , r ' ) ≠ $b=1\iff x\in L$$r'$$\{0,1\}^{f(|x|)}$$i$$r'$$A(x,r')\not= b$

Nachdem wir nun wissen, dass wir eine schlechte Wahl einer zufälligen Zeichenfolge in eine Beschreibung umsetzen können, wollen wir einige Bedingungen beobachten, die ausreichen, um unsere Beschreibung von in eine Komprimierung umzuwandeln. Um zu beschreiben , benötigen wir genügend Bits, um , , und dann den Code für unsere Prozedur (den Code für und die von uns beschriebene Routine) zu beschreiben, wobei die Länger x i b A | x | + | i | + O ( 1 ) = | x | + log 2 ( 2 f ( | x | ) ϵ ( x ) ) + O ( 1 ) = | x | + f ( | x | ) - log ( 1 / ϵ $r$$r$$x$$i$$b$$A$

Denken Sie daran, dass die Länge ist. Dies ist also eine Komprimierung von wenn z. B. wenn .f ( | x | ) r log ( 1 / ϵ ( x ) ) = | x | + Ω ( 1 ) , ε ( x ) = 1 / 2 2 | x $r$$f(|x|)$$r$

Beachten Sie schließlich, dass wenn eine Kolmogorov-Zufallszeichenfolge wäre, wir keine solche Komprimierung haben könnten. Solange die Fehlerwahrscheinlichkeit von ausreichend klein ist, bewirkt eine Kolmogorov-Zufallszeichenfolge anstelle der Folge von Zufallsbits, dass antwortet korrekt!A $r$$A$$A$

Beachten Sie, dass das einzige, was wir an , die geringe Fehlerwahrscheinlichkeit ist. Es ist uns egal, ob eine extrem lange Laufzeit hat oder ob einen ein- oder zweiseitigen Fehler hat.A $A$$A$$A$

Wenn wir dies auf die Frage von (oder oder ) , heißt es, dass wir, solange wir die Fehlerwahrscheinlichkeit unserer Algorithmen , Kolmogorov-Zufallszeichenfolgen anstelle ihrer Zufallsbits verwenden können.c o R P B P $RP$$coRP$$BPP$

... aber nur wenn wir zuerst verstärken.

Eine Folgefrage könnte lauten: "Kann ich dies tun, ohne die Fehlerwahrscheinlichkeit zu erhöhen?" Betrachten Sie den folgenden Algorithmus der und eine Fehlerwahrscheinlichkeit von 1/2 .{ 0 , 1 } * 1 / 2 $A$$\{0,1\}^*$$1/2^n$

Bei Eingabe :$x$

• Generieren Sie eine Zeichenfolge$r\in\{0,1\}^n$
• Wenn , ablehnen.$r=x$
• Akzeptieren.

Beachten Sie, dass es für jede Wahl von eine Auswahl von so dass auf fehlerhaft ist , nämlich die Wahl von , die , so dass wir die zufällige Folge von Bits, die von verwendet werden, nicht durch eine Kolmogorov-Zufallszeichenfolge ersetzen können, ohne sie zu verstärken es ist Fehlerwahrscheinlichkeit!x A x r x $r$$x$$A$$x$$r$ $x$$A$

Ein Hinweis zur Quelle: Ich bin mir nicht sicher, ob dies neu ist, aber ich habe das erste Argument in meine Beschreibung für meine Eignungsprüfung aufgenommen, die nach Abschluss der Überarbeitung online verfügbar sein wird.