# Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?

$\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}$?

• This is pretty basic complexity theory material, I don't think it belongs on this site. Aug 15 '15 at 14:14

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.