Published by MIT Press. Copyright 1996 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe for legitimate access to all journal articles.

Abstract

In 1978, Hartmanis conjectured that there exist no sparse complete sets for P under logspace many-one reductions. In this paper, in support of the conjecture, it is shown that if P has sparse hard sets under logspace many-one reductions, then P is a subset of DSPACE[log^2 n].

• Preformatted versions of the article
  • DVI (49,976 bytes)
  • PostScript (204,339 bytes)
  • PDF (212,225 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX (cj96-02.tex, 38,076 bytes)
  • BIBTeX (cj96-02.bib, 4,381 bytes)
  • Parameter settings for custom formatting (cjropts.tex, 117 bytes)
  • Self citation in BIBTeX (265 bytes)
• Online discussion
• Instructions for Readers

DOI: 10.4086/cjtcs.1996.002

---

Article 1 Article 3
Volume 1996 Published articles

Last modified: 24 March 1997