Using self-reducibilities to characterize polynomial time

Judy Goldsmith, Deborah Joseph, Paul Young

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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.

Original languageEnglish
Pages (from-to)288-308
Number of pages21
JournalInformation and Computation
Issue number2
StatePublished - Jun 1993

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Using self-reducibilities to characterize polynomial time'. Together they form a unique fingerprint.

Cite this