On Reducibility to Complex or Sparse Sets
Nancy Ann Lynch · Journal of the ACM · 1975
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.