EASILY CHECKED GENERALIZED SELF-REDUCIBILITY

This paper explores two generalizations within NP of self-reducibility: Arvind and Biswas's kernel constructibility and Khadilkar and Biswas's committability. Informally stated, kernel constructible sets have (generalized) self-reductions that are easy to check, though perhaps hard to compute, and committable sets are those sets for which the potential correctness of a partial proof of set membership can be checked via a query to the same set (that is, via a self-reduction). We study these two notions of generalized self-reducibility on nondense sets. We show that sparse kernel constructible sets are of low complexity, extend previous results showing that sparse committable sets are of low complexity, and provide structural evidence of interest in its own right-namely, that if all sparse disjunctively self-reducible sets are in P then FewP boolean AND coFewP is not P-bi-immune-that our extension is unlikely to be extended further. We obtain density-based sufficient conditions for kernel-constructibility: sets whose complements are captured by nondense sets are perforce kernel constructible. Using sparse languages and Kolmogorov complexity theory as tools, we argue that kernel constructibility is orthogonal to standard notions of complexity.