1
$\begingroup$

Suppose we have a BPP algorithm $A$ s.t. its running time is random and is $O(n^2)$ in expectation. How do we create a new BPP algorithm $B$ to solve the same problem s.t. it has deterministic running time $O(n^2)$?

My effort: Denote the running time of $A$ as $T$. Suppose $E(T)\leq T(n)=O(n^2)$.

  1. Run $A$ at most $kT(n)$ steps.
  2. If it terminates, return its output; otherwise, output Yes with probability $q$.

But I just proved that this cannot be a BPP algorithm for any $q$... Any hint please?

$\endgroup$
3
  • $\begingroup$ Your approach works. $\endgroup$ Nov 1 '20 at 6:23
  • 1
    $\begingroup$ Note this is not what is usually referred to by derandomization. $\endgroup$ Nov 1 '20 at 6:24
  • 1
    $\begingroup$ The algorithm $B$ is still randomized, and allowed to make mistakes. The only deterministic thing about it is its running time. $\endgroup$ Nov 1 '20 at 6:53
3
$\begingroup$

Derandomization is the process in which a randomized algorithm is converted to an equivalent deterministic algorithm. This is not what this exercise is asking you to do. The algorithm $B$ is still randomized – only its running time is deterministic.

Suppose that $A$ decides the problem $L$, in the following sense: if $x \in L$ then $\Pr[A(x) = 1] \geq 2/3$, and if $x \notin L$ then $\Pr[A(x) = 0] \geq 2/3$. Moreover, there is a function $f(n) = O(n^2)$ such that the expected running time of $A$ on $x$ is always at most $f(|x|)$. We want to construct a new algorithm $B$ with the same behavior regarding to $L$, and with the following additional property: there is a function $g(n) = O(n^2)$ such that the running time of $B$ on $x$ is exactly $g(|x|)$.

Suppose that $f(n) = Cn^2$, and consider your solution with $K = 3C$ and $q=1/2$. If we're careful, then there will exist a function $g(n) = O(n^2)$ such that the running time of $B$ on $x$ is exactly $g(|x|)$. What about the other property?

Suppose that $x \in L$ has size $|x|=n$. The expected running time of $A$ on $x$ is at most $f(n) = Cn^2$, and so $A$ terminates within $Kn^2$ steps with probability $p \geq 2/3$. If this happens, the probability that $B$ outputs $1$ is at least $2/3$. Otherwise, the probability that $B$ outputs $1$ is $1/2$. In 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}.$$ Similarly, if $x \notin L$ then $\Pr[B(x) = 0] \geq 11/18$. This is almost what we want – we want $11/18$ to be replaced by $2/3$.

In order to enhance the success probability ("error reduction"), we need to run $A$ several times and take a majority vote. By running $A$ enough times and by increasing the value of $K$, we get drive the error probability of $B$ down to any positive constant. Details left to you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.