## Abstract

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 NL{square image of or equal to}SC (respectively P{square image of or equal to}SC, β_{k}, or PH{square image of or equal to}SC), and if P has subpolynomially sparse logspace-hard sets, then P≠PSPACE.

Original language | English (US) |
---|---|

Pages (from-to) | 262-296 |

Number of pages | 35 |

Journal | Computational Complexity |

Volume | 4 |

Issue number | 3 |

DOIs | |

State | Published - Sep 1994 |

Externally published | Yes |

## Keywords

- Subject classifications: 68Q15, 03D15

## ASJC Scopus subject areas

- Theoretical Computer Science
- Mathematics(all)
- Computational Theory and Mathematics
- Computational Mathematics