<p>$\mathsf{L}=\mathsf{NL}$. Yes, there is an analog of Mahaney's Theorem for log-space. If there is a sparse set that is hard for $\mathsf{NL}$ under logspace reductions, then $\mathsf{L}=\mathsf{NL}$:</p>

<p>J.-Y. Cai and D. Sivakumar. <a href="http://dx.doi.org/10.1016/S0304-3975(99)00234-0" rel="nofollow">Resolution of Hartmanis’ conjecture for NL-hard sparse sets</a>. Theoret. Comp. Sci. 240(2):257–269, 2000.</p>

<p>van Melkebeek extends this to logspace bounded truth-table reductions, which is quite close to the state of the art for extensions of Mahaney's Theorem in the polytime world as well:</p>

<p>D. van Melkebeek. <a href="http://dx.doi.org/10.1006/jcss.1998.1589" rel="nofollow">Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets</a>. J. Comput. Syst. Sci. 57(2):213-232, 1998.</p>

<p>(I think the reversed dates are simply because these are the journal publications rather than the corresponding conference publications.)</p>

CC BY-SA 3.0
2013-01-28T16:51:31.500Z
2013-01-28T18:01:19.207Z
2013-01-28T18:01:19.207Z
Joshua Grochow
<p>What are the consequences of a sparse language being complete for $\mathsf{NSPACE(\log n)}$ under deterministic $O(\log n)$-space many-one reductions? Is there an analog of Mahaney's Theorem for $\mathsf{NL}$ (if there is a sparse $\mathsf{NL}$-complete language then $\mathsf{L} = \mathsf{NL}$)?</p>

<p>Bounded here was meant to indicate that if the input alphabet is $\{a_1, ..., a_k\}$, the language is a subset of $a_1^* a_2^* ... a_k^*$. Any such language clearly has number of strings of length $n$ that is bounded by $n^k$ so bounded => sparse. </p>

CC BY-SA 3.0
2013-01-22T20:01:33.270Z
By "bounded", you mean having a polynomial number of positive instances of a given length, as in Mahaney's theorem, right?
David Eppstein
<cc.complexity-theory><conditional-results>
bounded language complete for NSPACE(log n)?
user13417
# bounded language complete for NSPACE(log n)?

(Asked by: username_0 on 2013-01-22)

What are the consequences of a sparse language being complete for $\mathsf{NSPACE(\log n)}$ under deterministic $O(\log n)$-space many-one reductions? Is there an analog of Mahaney's Theorem for $\mathsf{NL}$ (if there is a sparse $\mathsf{NL}$-complete language then $\mathsf{L} = \mathsf{NL}$)?

Bounded here was meant to indicate that if the input alphabet is $\{a\_1, ..., a\_k\}$, the language is a subset of $a\_1^\* a\_2^\* ... a\_k^\*$. Any such language clearly has number of strings of length $n$ that is bounded by $n^k$ so bounded => sparse.

**Tags:** cc.complexity-theory, conditional-results

> **Comments:**
> **username_1**: By "bounded", you mean having a polynomial number of positive instances of a given length, as in Mahaney's theorem, right?  

---

## 1 answers

### Answer by username_2 on 2013-01-28. Score: 3

$\mathsf{L}=\mathsf{NL}$. Yes, there is an analog of Mahaney's Theorem for log-space. If there is a sparse set that is hard for $\mathsf{NL}$ under logspace reductions, then $\mathsf{L}=\mathsf{NL}$:

J.-Y. Cai and D. Sivakumar. [Resolution of Hartmanis’ conjecture for NL-hard sparse sets](http://dx.doi.org/10.1016/S0304-3975(99)00234-0). Theoret. Comp. Sci. 240(2):257–269, 2000.

van Melkebeek extends this to logspace bounded truth-table reductions, which is quite close to the state of the art for extensions of Mahaney's Theorem in the polytime world as well:

D. van Melkebeek. [Deterministic and Randomized Bounded Truth-Table Reductions of P, NL, and L to Sparse Sets](http://dx.doi.org/10.1006/jcss.1998.1589). J. Comput. Syst. Sci. 57(2):213-232, 1998.

(I think the reversed dates are simply because these are the journal publications rather than the corresponding conference publications.)


---

