Saving queries with randomness

The power of randomness to save a query to an NP-complete set is studied. Error probabilities for the random reduction of the P ^SAT||^[k]⩽_m^P-complete language to a language in P^SAT||[k-1] are obtained. It is proved that these probability bounds are tight unless PH collapses. Tight performance bounds on several randomized reductions between classes in the Boolean hierarchy are also obtained. These bounds provide probability thresholds for completeness under randomized reductions in these classes. Using these thresholds, hardness properties are proved for some languages in the Boolean hierarchy that are not known to be ⩽_m^P-complete. It is also shown that randomness is far less effective in saving a query in bounded query function computations