On coherence, random-self-reducibility, and self-correction

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 determ ine 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 D if one can convert a program that is correct on most of the probability mass of D to a probabilistic program th at 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 coh erence, even if the nonadaptive querier is nonuniform. Blum et al. (1993) s howed that every random-self-reducible function is self-correctable. It is unknown, however, whether self-correctability implies random-self-reducibil ity. We show, assuming a reasonable complexity-theoretic hypothesis, that c ertain hard, sparse, tally sets exist, and that there is a self-correctable function which is not random-self-reducible. For easily samplable distribu tions, 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.