dérandomiser un algorithme BPP

Question

Supposons que nous ayons un algorithme BPP $A$ sa durée de fonctionnement est aléatoire et est $O(n^2)$dans l'attente. Comment créer un nouvel algorithme BPP$B$ pour résoudre le même problème st il a un temps de fonctionnement déterministe $O(n^2)$?

Mon effort: désigne le temps de fonctionnement de $A$ comme $T$. Supposer$E(T)\leq T(n)=O(n^2)$.

1. Cours $A$ au plus $kT(n)$ pas.
2. S'il se termine, renvoie sa sortie; sinon, affichez Oui avec probabilité$q$.

Mais je viens de prouver que cela ne peut pas être un algorithme BPP pour aucun $q$... Un indice, s'il vous plaît?

Answer 1

La dérandomisation est le processus dans lequel un algorithme aléatoire est converti en un algorithme déterministe équivalent. Ce n'est pas ce que cet exercice vous demande de faire. L'algorithme$B$ est toujours aléatoire - seule sa durée de fonctionnement est déterministe.

Supposer que $A$ décide du problème $L$, dans le sens suivant: si $x \in L$ ensuite $\Pr[A(x) = 1] \geq 2/3$, et si $x \notin L$ ensuite $\Pr[A(x) = 0] \geq 2/3$. De plus, il y a une fonction$f(n) = O(n^2)$ de telle sorte que la durée de fonctionnement prévue de $A$ au $x$ est toujours au plus $f(|x|)$. Nous voulons construire un nouvel algorithme$B$ avec le même comportement vis-à-vis de $L$, et avec la propriété supplémentaire suivante: il y a une fonction $g(n) = O(n^2)$ de telle sorte que le temps de fonctionnement de $B$ au $x$est exactement $g(|x|)$.

Supposer que $f(n) = Cn^2$et considérez votre solution avec $K = 3C$ et $q=1/2$. Si on fait attention, alors il y aura une fonction$g(n) = O(n^2)$ de telle sorte que le temps de fonctionnement de $B$ au $x$ est exactement $g(|x|)$. Qu'en est-il de l'autre propriété?

Supposer que $x \in L$ a la taille $|x|=n$. La durée de fonctionnement prévue de$A$ au $x$ est au plus $f(n) = Cn^2$, et donc $A$ se termine dans $Kn^2$ étapes avec probabilité $p \geq 2/3$. Si cela se produit, la probabilité que$B$ les sorties $1$ Est au moins $2/3$. Sinon, la probabilité que$B$ les sorties $1$ est $1/2$. Au total,$$\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}.$$ De même, si $x \notin L$ ensuite $\Pr[B(x) = 0] \geq 11/18$. C'est presque ce que nous voulons - nous voulons$11/18$ à remplacer par $2/3$.

Afin d'améliorer la probabilité de succès ("réduction des erreurs"), nous devons exécuter $A$plusieurs fois et prendre un vote à la majorité. En exécutant$A$ suffisamment de fois et en augmentant la valeur de $K$, nous obtenons la probabilité d'erreur de $B$jusqu'à n'importe quelle constante positive. Détails laissés à vous.