Sparse P-hard sets yield space-efficient algorithms
Mitsunori Ogihara · 2002
J. Hartmanis (1978) 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/spl sube/DSPACE[log/sup 2/n]. The result follows from a more general statement: if P has 2/sup polylog/ sparse hard sets under poly-logarithmic space-computable many-one reductions, then P/spl sube/DSPACE[polylog].