On reducibility to complex or sparse sets

ABSTRACT. Sets which are efficiently reducible (in Karp's sense) to arbitrarily complex sets are shown to be polynomial computable. Analogously, sets efficiently reducible to arbitrarily sparse sets are polynomial computable. A key lemma for both proofs shows that any set which is not polynomial computable has an infinite recursive subset of its domain, on which every algorithm runs slowly on almost all arguments. KEY WORDS AND PHRASES. " polynomial time reducibility, a.e. complexity, many-one reducibility, complexity core CR CATEGORmS: 5.25, 5.26 1