# The Power of Randomized Reduction

I try to figure out a redundant power of two-sided error randomized Karp - reduction.

It's well known fact and it is relatively hard to show that BPP is reducible by a one-sided error randomized Karp-reduction to coRP (in case of promise problem).

Without delving into details it make sense that the combination of the one - sided error probability of the reduction and the one-sided error probability of coRP leads to two-sided error probability of BPP. Of course the proof of that is not so intuitive.

The question it is possible by two-sided error randomized Karp-reduction to reduce BPP to some constant set in P? In the light of the power of one - sided randomized Karp - reduction, it make sense that two-sided randomized Karp - reduction is strong enough to reduce BPP to constant set, but how to show it formally?

We can think of a BPP algorithm $A$ for a language $L$ as accepting two inputs, the real input $x$ and a random string $r$, whose length is polynomial in $x$. Now take the Boolean circuit evaluation problem, which is P-complete. Since $A(x,r) \in P$, we can reduce $A$ to this problem, substituting random $r$. Then if $x \in L$ then the reduction yields a YES instance with probability at least $2/3$, and if $x \notin L$ then it yields a NO instance with probability at least $2/3$.