10
$\begingroup$

Mahaney's Theorem tells us that if there is a sparse $NP$-complete set under polynomial-time many-one reductions, then $P = NP$. (See "Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis")

Are there known consequences of the existence of sparse complete sets for other complexity classes? In particular, if there is a sparse $P$-complete set under logspace many-one reductions, does that imply $P = L$?

$\endgroup$
10
$\begingroup$

Yes, exactly what you suggested is true: if there is a sparse $\mathbf{P}$-complete set under log-space many-one reductions, then $\mathbf{P} = \mathbf{L}$. This was conjectured by Hartmanis in 1978 and proven by Cai and Sivakumar in 1995. See this paper.

Hartmanis also conjectured that if there is a sparse $\mathbf{NL}$-complete set under log-space many-one reductions, then $\mathbf{NL} = \mathbf{L}$. This was also proven by Cai and Sivakumar in 1997; see this other paper.

$\endgroup$
  • $\begingroup$ Wow! Thank you so much!! This is great. :) $\endgroup$ – Michael Wehar Jan 18 '18 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.