<p>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 <a href="http://ieeexplore.ieee.org/document/492492/" rel="noreferrer">this paper</a>.</p>

<p>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 <a href="http://pages.cs.wisc.edu/~jyc/papers/NL.pdf" rel="noreferrer">this other paper</a>.</p>

CC BY-SA 3.0
2018-01-18T18:23:40.717Z
Wow!  Thank you so much!!  This is great.  :)
Michael Wehar
CC BY-SA 3.0
2018-01-18T17:30:36.767Z
2018-01-18T17:30:36.767Z
William Hoza
<p>Mahaney's Theorem tells us that if there is a sparse $NP$-complete set under polynomial-time many-one reductions, then $P = NP$.  (See "<a href="http://www.sciencedirect.com/science/article/pii/0022000082900022" rel="noreferrer">Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis</a>")</p>

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

<cc.complexity-theory><complexity-classes><reductions><polynomial-time><logspace>
On sparse complete sets and P vs L
Michael Wehar
# On sparse complete sets and P vs L

(Asked by: username_0 on 2018-01-18)

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](http://www.sciencedirect.com/science/article/pii/0022000082900022)")

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

**Tags:** cc.complexity-theory, complexity-classes, reductions, polynomial-time, logspace

---

## 1 answers

### Answer by username_1 on 2018-01-18. Score: 11 | Accepted answer

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](http://ieeexplore.ieee.org/document/492492/).

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](http://pages.cs.wisc.edu/~jyc/papers/NL.pdf).

> **Comments:**
> **username_0**: Wow!  Thank you so much!!  This is great.  :)  

---

