文章基本信息
- 标题：Sparse Hard Sets for P Yield Space-Efficient Algorithms
- 本地全文：下载
- 作者：Mitsunori Ogihara
- 期刊名称：Chicago Journal of Theoretical Computer Science
- 印刷版ISSN：1073-0486
- 出版年度：1996
- 卷号：1996
- 出版社：MIT Press ; University of Chicago, Department of Computer Science
- 摘要：
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].
