Saving Queries With Randomness

In this paper, we provide tight bounds on the success probabilities of randomized reductions between various classes in the Boolean and Bounded Query Hierarchies. The P$^{SAT\Vert[k]}$ $\leq^{P}_{m}$ - complete language randomly reduces to a language in P$^{SAT\Vert[k-1]}$ with a one-sided error probability of 1/$\lceil$k/2$\rceil$. If two-sided error is allowed, then we show that a much lower error probability of 1/($k$ + 1) can be achieved. We prove that both these reductions are almost optimal by showing that the error probabilities cannot be reduced by even 1/poly, unless the PH collapses. These tight bounds precisely characterize the power and limitations of randomness in saving a query to SAT. These results can be used to identify optimal probability thresholds which determine when languages complete under randomized reductions inherit the hardness properties associated with $\leq^{P}_{m}$ - complete languages. Using these thresholds we prove hardness properties for some languages in these classes which are not $\leq^{P}_{m}$ - complete in certain relativized worlds. We also explore the relationship between randomization and functions computable using bounded queries to SAT. For any function $h (n) = O(log $n$), we show that there is a function $f$ computable using $h(n)$ nonadaptive queries to SAT, which cannot be computed correctly with probability 1/2+1/poly by any randomized machine which makes less than $h(n)$ adaptive queries to any oracle, unless PH collapses