4
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ By "bounded", you mean having a polynomial number of positive instances of a given length, as in Mahaney's theorem, right? $\endgroup$
    – David Eppstein
    Jan 22, 2013 at 20:01

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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