Chicago Journal of Theoretical Computer Science

Volume 1996

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

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].

DOI: 10.4086/cjtcs.1996.002
[] Article 1 [] Article 3
[back] Volume 1996 [back] Published articles
[CJCTS home]

Last modified: 24 March 1997