Saving Queries With Randomness

Other Titles
Abstract
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.
Journal / Series
Volume & Issue
Description
Sponsorship
Date Issued
1991-12
Publisher
Cornell University
Keywords
computer science; technical report
Location
Effective Date
Expiration Date
Sector
Employer
Union
Union Local
NAICS
Number of Workers
Committee Chair
Committee Co-Chair
Committee Member
Degree Discipline
Degree Name
Degree Level
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
References
Link(s) to Reference(s)
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1259
Government Document
ISBN
ISMN
ISSN
Other Identifiers
Rights
Rights URI
Types
technical report
Accessibility Feature
Accessibility Hazard
Accessibility Summary
Link(s) to Catalog Record