Sparse Hard Sets for P Yield Space-Efficient Algorithms
Mitsunori Ogihara · 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 ` DSPACE[log 2 n]. The result is derived from a more general statement that if P has 2 polylog sparse hard sets under poly-logarithmic space-computable many-one reductions, then P ` DSPACE[polylog]. 1 Introduction In 1978, Hartmanis conjectured that no P-complete sets under logspace many-one reductions can be polynomially sparse; i.e., for any P-complete set A, k fx 2 A j jxj ng k cannot be bounded by any polynomial in n [5]. The conjecture is interesting and fascinating. If the conjecture is true, then L 6= P, because L = P implies any nonempty finite set being P-complete. So, with expectation that L is different from P, one might believe the validity of the conjecture. Nevertheless, such a reasoning would be fallacious, for, proving thi...