Space-efficient recognition of sparse self-reducible languages

Mahaney and others have shown that sparse self-reducible sets have time-efficient algorithms, and have concluded that it is unlikely that NP has sparse complete sets. Mahaney's work, intuition, and a 1978 conjecture of Hartmanis notwithstanding, nothing has been known about the density of complete sets for feasible classes until now. This paper shows that sparse self-reducible sets have space-efficient algorithms, and in many cases, even have time-space-efficient algorithms. We conclude that NL, NC^k, AC^k, LOG(DCFL), LOG(CFL), and P lack complete (or even Turing-hard) sets of low density unless implausible complexity class inclusions hold. In particular, if NL (respectively P,_k, or NP) has a polylog-sparse logspace-hard set, then NLSC (respectively PSC,_k, or PHSC), and if P has subpolynomially sparse logspace-hard sets, then PPSPACE.