Title :
The resolution of a Hartmanis conjecture
Author :
Cai, Jin-Yi ; Sivakumar, D.
Author_Institution :
Dept. of Comput. Sci., State Univ. of New York, Buffalo, NY, USA
Abstract :
Building on the recent breakthrough by M. Ogihara (1995), we resolve a conjecture made by J. Hartmanis (1978) regarding the (non) existence of sparse sets complete for P under logspace many-one reductions. We show that if there exists a sparse hard set for P under logspace many-one reductions, then P=LOGSPACE. We further prove that if P has a sparse hard set under many-one reductions computable in NC1 , then P collapses to NC1
Keywords :
computational complexity; Hartmanis conjecture; logspace many-one reductions; sparse hard set; sparse sets; Circuits; Complexity theory; Computer science; NP-complete problem; Polynomials;
Conference_Titel :
Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on
Conference_Location :
Milwaukee, WI
Print_ISBN :
0-8186-7183-1
DOI :
10.1109/SFCS.1995.492492
