ISSN:
1420-8954
Keywords:
Key words. self‐reducibility; self‐correction; coherence.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract. We study three types of self‐reducibility that are motivated by the theory of program verification. A set A is random‐self‐reducible if one can determine whether an input x is in A by making random queries to an A‐oracle. The distribution of each query may depend only on the length of x. A set B is self‐correctable over a distribution ${\cal D}$ if one can convert a program that is correct on most of the probability mass of ${\cal D}$ to a probabilistic program that is correct everywhere. A set C is coherent if one can determine whether an input x is in C by asking questions to an oracle for C–{x}.¶We first show that adaptive coherence is more powerful than nonadaptive coherence, even if the nonadaptive querier is nonuniform. Blum et al.(1993) showed that every random‐self‐reducible function is self‐correctable. It is unknown, however, whether self‐correctability implies random‐self‐reducibility. We show, assuming a reasonable complexity‐theoretic hypothesis, that certain hard, sparse, tally sets exist, and that there is a self‐correctable function which is not random‐self‐reducible. For easily samplable distributions, however, we show that constructing a self‐correctable function that is not random‐self‐reducible is as hard as proving that P is different from PP.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s000370050009
Permalink
