# 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

## 1 Answer

$\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. 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. 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.)