It is conjectured that randomness does not extend the power of polynomial time algorithms, that is, ${\bf P}={\bf BPP}$ is conjectured to hold. On the other hand, randomness seems to have a quite different effect on polynomial time reductions. By the well known result of Valiant and Vazirani, $SAT$ reduces to $USAT$ via randomized polynomial time reduction. It is not likely that the reduction could be derandomized, since it would yield ${\bf NP}={\bf UP}$, which is thought unlikely.I wonder, what could be the reason for this asymmetric situation: derandomization seems quite possible in probabilistic polynomial time algorithms, but not in  probabilistic polynomial time reductions?
Why does randomness have stronger effect on reductions than on algorithms?
cc.complexity theory;reductions;derandomization