Using self-reducibilities to characterize polynomial time

Abstract In this paper we study the effect that the self-reducibility properties of a set have on its time complexity. In particular, we show that the extent to which a set is self-reducible can determine whether or not the set is polynomially decidable. Our results concern three variations on the notion of Turing self-reducibility: near-testability , word decreasing query ( wdq ) self-reducibility , and p-cheatability . Our first pair of results provide charaterizations of polynomial time by coupling the notion, first of Turing self-reducibility, then of near-testability, with the notion of p -cheatability. We believe that these are among the first nontrivial structural characterizations of polynomial time. In contrast, our final theorems show that if sufficiently large deterministic and nondeterministic time classes are separated by tally sets, then (a) we cannot similarly characterize polynomial time by coupling word decreasing query self-reducibility with a variant of p -cheatability, and (b) we cannot characterize polynomial time by coupling ⊕ P and p -cheatability.