# bounded language complete for NSPACE(log n)?

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.

• By "bounded", you mean having a polynomial number of positive instances of a given length, as in Mahaney's theorem, right? – David Eppstein Jan 22 '13 at 20:01

$\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}$: