Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR96-014 | 14th February 1996 00:00

Sparse Hard Sets for P Yields Space-Efficient Algorithms

RSS-Feed




TR96-014
Authors: Mitsunori Ogihara
Publication: 16th February 1996 22:43
Downloads: 3362
Keywords: 


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 included in DPSPACE[log^2 n].



ISSN 1433-8092 | Imprint