Resolution of Hartmanis' conjecture for NL-hard sparse sets

Authors
Cai, JY Sivakumar, D
Citation
Jy. Cai et D. Sivakumar, Resolution of Hartmanis' conjecture for NL-hard sparse sets, THEOR COMP, 240(2), 2000, pp. 257-269
Citations number
22
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
240
Issue
2
Year of publication
2000
Pages
257 - 269
Database
ISI
SICI code
0304-3975(20000617)240:2<257:ROHCFN>2.0.ZU;2-6
Abstract
We resolve a conjecture of Hartmanis from 1978 about sparse hard sets for n ondeterministic logspace (NL). We show that there exists a sparse hard set S for NL under logspace many-one reductions if and only if NL = L (determin istic logspace). (C) 2000 Elsevier Science B.V, All rights reserved.