-2
$\begingroup$

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

$\endgroup$
1
  • 8
    $\begingroup$ This is pretty basic complexity theory material, I don't think it belongs on this site. $\endgroup$ Aug 15, 2015 at 14:14

1 Answer 1

11
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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