"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 averagecase 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 kbit vector that is not equal to the kbit vector of solutions to the k instances. A decision problem with this property is called kmembership comparable.
Amir, Beigel, and Gasarch (1990) show that for constant k, all kmembership 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
kmembership comparable
if
using l help bits, k instances of the problem can be efficiently solved with probability greater than 2^{l−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 nonvanishing probability.
We note that when k is constant, kmembership comparability implies being in ¶ / \poly.
Next we consider the setting of averagecase 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
superlogarithmic, assuming kmembership 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
