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$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Wow! Thank you so much!! This is great. :) $\endgroup$
    – Michael Wehar
    Commented Jan 18, 2018 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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