einen BPP-Algorithmus derandomisieren

Question

Angenommen, wir haben einen BPP-Algorithmus $A$ st seine Laufzeit ist zufällig und ist $O(n^2)$in Erwartung. Wie erstellen wir einen neuen BPP-Algorithmus?$B$ Um das gleiche Problem zu lösen, hat es eine deterministische Laufzeit $O(n^2)$?

Meine Anstrengung: Bezeichne die Laufzeit von $A$ wie $T$. Annehmen$E(T)\leq T(n)=O(n^2)$.

1. Lauf $A$ maximal $kT(n)$ Schritte.
2. Wenn es beendet wird, geben Sie seine Ausgabe zurück. Andernfalls geben Sie Ja mit Wahrscheinlichkeit aus$q$.

Aber ich habe gerade bewiesen, dass dies für keinen BPP-Algorithmus sein kann $q$... Irgendwelche Hinweise bitte?

Answer 1

Derandomisierung ist der Prozess, bei dem ein randomisierter Algorithmus in einen äquivalenten deterministischen Algorithmus umgewandelt wird. Dies ist nicht das, worum Sie in dieser Übung gebeten werden. Der Algorithmus$B$ ist immer noch randomisiert - nur seine Laufzeit ist deterministisch.

Nehme an, dass $A$ entscheidet das Problem $L$im folgenden Sinne: wenn $x \in L$ dann $\Pr[A(x) = 1] \geq 2/3$, und wenn $x \notin L$ dann $\Pr[A(x) = 0] \geq 2/3$. Darüber hinaus gibt es eine Funktion$f(n) = O(n^2)$ so dass die erwartete Laufzeit von $A$ auf $x$ ist immer höchstens $f(|x|)$. Wir wollen einen neuen Algorithmus konstruieren$B$ mit dem gleichen Verhalten in Bezug auf $L$und mit der folgenden zusätzlichen Eigenschaft: Es gibt eine Funktion $g(n) = O(n^2)$ so dass die Laufzeit von $B$ auf $x$ist genau $g(|x|)$.

Nehme an, dass $f(n) = Cn^2$und überlegen Sie sich Ihre Lösung mit $K = 3C$ und $q=1/2$. Wenn wir vorsichtig sind, wird es eine Funktion geben$g(n) = O(n^2)$ so dass die Laufzeit von $B$ auf $x$ ist genau $g(|x|)$. Was ist mit der anderen Immobilie?

Nehme an, dass $x \in L$ hat Größe $|x|=n$. Die erwartete Laufzeit von$A$ auf $x$ ist höchstens $f(n) = Cn^2$, und so $A$ endet innerhalb $Kn^2$ Schritte mit Wahrscheinlichkeit $p \geq 2/3$. Wenn dies passiert, ist die Wahrscheinlichkeit, dass$B$ Ausgänge $1$ ist mindestens $2/3$. Ansonsten ist die Wahrscheinlichkeit, dass$B$ Ausgänge $1$ ist $1/2$. In Summe,$$\Pr[B(x) = 1] \geq p \cdot \frac{2}{3} + (1-p) \cdot \frac{1}{2} = \frac{1}{2} + p \cdot \frac{1}{6} \geq \frac{1}{2} + \frac{2}{3} \cdot \frac{1}{6} = \frac{11}{18} > \frac{1}{2}.$$ Ebenso wenn $x \notin L$ dann $\Pr[B(x) = 0] \geq 11/18$. Das ist fast was wir wollen - wir wollen$11/18$ ersetzt werden durch $2/3$.

Um die Erfolgswahrscheinlichkeit zu erhöhen ("Fehlerreduzierung"), müssen wir laufen $A$mehrmals und mehrheitlich abstimmen. Durch Laufen$A$ genug mal und durch Erhöhen des Wertes von $K$erhalten wir die Fehlerwahrscheinlichkeit von fahren $B$bis auf eine positive Konstante. Details bleiben Ihnen überlassen.