**Authors:** Richard Beigel and Joan Feigenbaum

**Abstract:**
Trakhtenbrot calls a set *A* *autoreducible* if *A* is
Turing-reducible to *A* via an oracle Turing machine that never
queries the oracle about the input string. Yao considers sets that
are autoreducible via probabilistic, polynomial-time oracle Turing
machines, and he calls such sets *coherent*. We continue the
study of autoreducible sets, including those that are autoreducible
via a family of polynomial-sized circuits, which we call *weakly
coherent*. Sets that are not weakly coherent are called
*strongly incoherent*. We show

- If
*s*is superpolynomial and space-constructible, then there is a strongly incoherent set in DSPACE(*s*(*n*)). - If NEEEXP is not a subset of BPEEEXP, then there is a set in NP that is incoherent.
- If
*A*is complete for any of the classes Σ_{i}^{p}, Π_{i}^{p}, or Δ_{i}^{p},*i*≥ 0, then*A*is coherent. In particular, all NP-complete sets are coherent.