On being incoherent without being very hard

Title: On being incoherent without being very hard

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.

As corollaries, we obtain new lower bounds on program checkability and random-self-reducibility. These results answer open questions posed by Yao and by Blum and Kannan.

Download Full Paper