CJTCS Volume 1996 Article 2

Volume 1996

</a>

Article 2

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.

---

Sparse Hard Sets for P Yield Space-Efficient Algorithms

Mitsunori Ogihara ( University of Rochester ) 27 March 1996

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

---

Article 1 Article 3
Volume 1996 Published articles

Last modified: 24 March 1997