<p>Suppose you have a circuit which takes as input an advice string and a random string. (So this circuit would be in $BPP/Poly$ or something like that.)  You can convert this into a purely deterministic circuit, which takes a somewhat larger advice string, as follows.</p>

<p>There are $2^n$ possible inputs. By hypothesis about the circuit, each random string is good for any input with probability say $3/4$. (By good, I mean that the random string leads the circuit to output the correct value.) </p>

<p>Suppose you select randomly select a set $S$ consisting of $c n$ random strings (chosen uniformly at random with replacement), where $c$ is a large constant. Then, for any input, the probability that the number of selected strings good for that input is below $c n/2$ is $e^{-c' n}$, by the Chernoff bound. By taking $c$ sufficiently large, one can ensure that the probility is below $2^{-n}$.</p>

<p>By the union bound, the probability that the set $S$ is good for all the $2^n$ input is $&gt; 0$. This means, that there exists some such set $S$. So, fix some such set $S$ and hard-wire it into the circuit. Instead of taking a random string, the circuit evaluates at all the inputs in $S$ and outputs the majority vote. Now the circuit is derandomized, and is correct always.</p>

<p>Thus, $BPP/Poly = RP/poly = P/Poly$. So there is no need to consider randomness plus advice strings.</p>

CC BY-SA 3.0
2015-08-15T13:50:28.807Z
2015-08-15T13:50:28.807Z
David Harris
<p>$\mathsf{P/Poly}$ captures those problems that could be solved in polynomial time given some precomputed polynomial number of constants.</p>

<p>Is there an analogous complexity class in randomized world such as $\mathsf{ZPP/Poly}$, $\mathsf{RP/Poly}$, $\mathsf{coRP/Poly}$, $\mathsf{BPP/Poly}$ etc.? Or is there an intuitive reason why all such bounded error algorithms be removed of randomness to bring to $\mathsf{P/Poly}$?</p>

CC BY-SA 3.0
2015-08-15T14:14:31.197Z
This is pretty basic complexity theory material, I don't think it belongs on this site.
Sasho Nikolov
<cc.complexity-theory><complexity-classes><big-picture><randomized-algorithms><derandomization>
Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?
Turbo
# Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?

(Asked by: username_0 on 2015-08-15)

$\mathsf{P/Poly}$ captures those problems that could be solved in polynomial time given some precomputed polynomial number of constants.

Is there an analogous complexity class in randomized world such as $\mathsf{ZPP/Poly}$, $\mathsf{RP/Poly}$, $\mathsf{coRP/Poly}$, $\mathsf{BPP/Poly}$ etc.? Or is there an intuitive reason why all such bounded error algorithms be removed of randomness to bring to $\mathsf{P/Poly}$?

**Tags:** cc.complexity-theory, complexity-classes, big-picture, randomized-algorithms, derandomization
> **Comments:**
> **username_1**: This is pretty basic complexity theory material, I don't think it belongs on this site.  

---

## 1 answers

### Answer by username_2 on 2015-08-15. Score: 12 | Accepted answer

Suppose you have a circuit which takes as input an advice string and a random string. (So this circuit would be in $BPP/Poly$ or something like that.) You can convert this into a purely deterministic circuit, which takes a somewhat larger advice string, as follows.

There are $2^n$ possible inputs. By hypothesis about the circuit, each random string is good for any input with probability say $3/4$. (By good, I mean that the random string leads the circuit to output the correct value.)

Suppose you select randomly select a set $S$ consisting of $c n$ random strings (chosen uniformly at random with replacement), where $c$ is a large constant. Then, for any input, the probability that the number of selected strings good for that input is below $c n/2$ is $e^{-c' n}$, by the Chernoff bound. By taking $c$ sufficiently large, one can ensure that the probility is below $2^{-n}$.

By the union bound, the probability that the set $S$ is good for all the $2^n$ input is $> 0$. This means, that there exists some such set $S$. So, fix some such set $S$ and hard-wire it into the circuit. Instead of taking a random string, the circuit evaluates at all the inputs in $S$ and outputs the majority vote. Now the circuit is derandomized, and is correct always.

Thus, $BPP/Poly = RP/poly = P/Poly$. So there is no need to consider randomness plus advice strings.


---

