caa a22 4500 469033908 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19920301xx s 000 0 eng 10.1007/BF01276436 doi (NATIONALLICENCE)springer-10.1007/BF01276436 On being incoherent without being very hard [Elektronische Daten] [Richard Beigel, Joan Feigenbaum] Trakhtenbrot calls a setA autoreducible ifA is Turing-reducible toA 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 setscoherent. We continue the study of autoreducible sets, including those that are autoreducible via a family of polynomial-sized circuits, which we callweakly coherent. Sets that are not weakly coherent are calledstrongly incoherent. We show Ifs is superpolynomial and space-constructible, then there is a strongly incoherent set in DSPACE (s(n)). If NEEEXP $$ \nsubseteq $$ BPEEEXP, then there is a set in NP that is incoherent. IfA is complete for any of the classes ∑ i p , ∏ i p , or Δ i p ,i≥0, thenA is coherent. In particular, all NP-complete sets are coherent. As corollaries, we obtain new lower bounds onprogram checkability andrandom-self-reducibility. These results answer open questions posed by Yao and by Blum and Kannan. Birkhäuser Verlag, 1992 Autoreducibility nationallicence Incoherence nationallicence Program Checkability nationallicence Random-Self-Reducibility nationallicence 68Q15 nationallicence Beigel Richard Department of Computer Science, Yale University, Yale Station, P. O. Box 2158, 06520-2158, New Haven, CT, USA aut Feigenbaum Joan AT&T Bell Laboratories, Room 2C-473, 600 Mountain Avenue, 07974-0636, Murray Hill, NJ, USA aut computational complexity Birkhäuser-Verlag 2/1(1992-03-01), 1-17 1016-3328 2:1<1 1992 2 37 https://doi.org/10.1007/BF01276436 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01276436 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Beigel Richard Department of Computer Science, Yale University, Yale Station, P. O. Box 2158, 06520-2158, New Haven, CT, USA aut NATIONALLICENCE 700 1- Feigenbaum Joan AT&T Bell Laboratories, Room 2C-473, 600 Mountain Avenue, 07974-0636, Murray Hill, NJ, USA aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/1(1992-03-01), 1-17 1016-3328 2:1<1 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer