“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 15124 |
|
||||||
| Abstract: | |||||||
|
"Help bits" are some limited trusted information about an instance or instances of a computational problem
that may reduce the computational complexity of solving that instance or instances.
In this paper, we study the value of help bits in the settings of randomized and average-case complexity.
If k instances of a decision problem can be efficiently solved using l < k help bits, then without access to help bits one can efficiently
compute a k-bit vector that is not equal to the k-bit vector of solutions to the k instances. A decision problem with this property is called k-membership comparable.
Amir, Beigel, and Gasarch (1990) show that for constant k, all k-membership comparable language are in ¶/\poly.
We extend this result to the setting of randomized computation:
We show that for k at most logarithmic, the decision problem is
k-membership comparable
if
using l help bits, k instances of the problem can be efficiently solved with probability greater than 2l−k.
The same conclusion holds if using less than k(1 − h(α)) help bits (where h(·) is the binary entropy function), we can efficiently solve 1−α fraction of the instances correctly with non-vanishing probability.
We note that when k is constant, k-membership comparability implies being in ¶ / \poly.
Next we consider the setting of average-case complexity:
Assume that we can solve k instances of a decision problem
using some help bits whose entropy is less than k
when the k instances are drawn independently from a particular distribution.
Then we can efficiently solve an instance drawn from that distribution with probability better than 1/2.
Finally, we show that in the case where k is
super-logarithmic, assuming k-membership comparability of a decision problem, one cannot prove that the problem is in ¶/\poly by a
"relativizing" proof technique.
All previous known proofs in this area have been relativizing.
Download TeX format |
|||||||
| back to top | |||||||
