Sparse hard sets for P: Resolution of a conjecture of Hartmanis

Authors
Cai, JY Sivakumar, D
Citation
Jy. Cai et D. Sivakumar, Sparse hard sets for P: Resolution of a conjecture of Hartmanis, J COMPUT SY, 58(2), 1999, pp. 280-296
Citations number
30
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
ISSN journal
00220000 → ACNP
Volume
58
Issue
2
Year of publication
1999
Pages
280 - 296
Database
ISI
SICI code
0022-0000(199904)58:2<280:SHSFPR>2.0.ZU;2-5
Abstract
Building on a recent breakthrough by Ogihara, we reserve a conjecture made by Hartmanis in 1978 regarding the (non)existence of sparse sets complete f or P under logspace many-one reductions. Ne show that if there exists a spa rse hard set for P under logspace many-one reductions, then P = LOGSPACE. N e further prove that if P has a sparse hard set under many-one reductions c omputable in NC1, then P collapses to NC1, (C) 1999 Academic Press.