SAVING QUERIES WITH RANDOMNESS

In this paper, we investigate the power of randomness to save a query to an NP-complete set. We show that the P-SATI[k] less than or equal t o(m)(p)-complete language randomly reduces to a language in P-SATI[k-1 ] with a one-sided error probability of 1/[k/2] or a two sided-error p robability of 1/(k+1). Furthermore, we prove that these probability bo unds are tight; i.e., they cannot be improved by 1/poly, unless PH col lapses. We also obtain tight performance bounds for randomized reducti ons between nearby classes in the Boolean and bounded query hierarchie s. These bounds provide probability thresholds for completeness under randomized reductions in these classes. Using these thresholds, we sho w that certain languages in the Boolean hierarchy which are not less t han or equal to(m)(p)-complete in some relativized worlds, nevertheles s inherit many of the hardness properties associated with the less tha n or equal to(m)(p)-complete languages. Finally, we explore the relati onship between randomization and functions that are computable using b ounded queries to SAT. For any function h(n) = O(log n), we show that there is a function f computable using h(nj nonadaptive queries to SAT , which cannot be computed correctly with probability 1/2+1/poly by an y randomized machine which makes less than h(n) adaptive queries to an y oracle, unless PH collapses. (C) 1995 Academic Press, Inc.