SPARSE HARD SETS FOR P YIELD SPACE-EFFICIENT ALGORITHMS

Authors
OGIHARA M
Citation
M. Ogihara, SPARSE HARD SETS FOR P YIELD SPACE-EFFICIENT ALGORITHMS, Chicago journal of theoretical computer science, (2), 1996, pp. 1-13
Citations number
13
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Chicago journal of theoretical computer science → ACNP
ISSN journal
10730486
Issue
2
Year of publication
1996
Pages
1 - 13
Database
ISI
SICI code
1073-0486(1996):2<1:SHSFPY>2.0.ZU;2-A
Abstract
In 1978, Hartmanis conjectured that there exist no sparse complete set s 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 lo gspace many-one reductions, then P subset of or equal to DSPACE[log(2) n].