12
$\begingroup$

It is a well-known fact that $ \mathsf{NL} = \cup_{k>0} \mathsf{2NFA[k]} $, where $ \mathsf{2NFA[k]} $ is the class of languages recognized by two-way nondeterministic finite automata with $ k>0 $ input heads, shortly 2nfa(k).

I have two but similar questions:

Is there any known language in $ \mathsf{NL} $ requiring super-linear time, where the model is a standard space-bounded NTM having a read-only input tape and a read/write work tape?

Is there any known language recognized by some 2nfa(k) in super-linear time but not recognized by any 2nfa(k) in linear time?

Improve this question
$\endgroup$
6
  • $\begingroup$ I think both your questions are the same question. Do you have a reason for them being different, or are you just unsure? $\endgroup$
    – Luke Mathieson
    Commented Jul 25, 2012 at 13:50
  • 1
    $\begingroup$ @LukeMathieson: I am not sure whether for a given $ t(n) $ time bounded NTM, there exists an equivalent $ O(t(n)) $ time bounded 2nfa(k) for some $ k>0 $, and vice versa. $\endgroup$
    – Abuzer Yakaryilmaz
    Commented Jul 25, 2012 at 14:00
  • $\begingroup$ From the equivalence though, you know that every language in NL has a 2nfa(k) and that every language that has a 2nfa(k) is in NL. $\endgroup$
    – Luke Mathieson
    Commented Jul 25, 2012 at 14:17
  • $\begingroup$ @LukeMathieson: Yes! $\endgroup$
    – Abuzer Yakaryilmaz
    Commented Jul 25, 2012 at 14:25
  • 1
    $\begingroup$ In the first question, you wrote "requiring super-linear time," but in which computational model? $\endgroup$
    – Tsuyoshi Ito
    Commented Jul 26, 2012 at 13:19

1 Answer 1

Reset to default
4
$\begingroup$

I believe that the "state of the art" is that it is extremely hard to prove superlinear lower bounds even for NP-complete problems. If you're fine with conditional lower bounds, then the field of fine-grained complexity gives you many problems that are in P but require superlinear time under some assumptions. In this survey of fine-grained complexity there are several such problems and some of them are in NL (for example there is an obvious NL algorithm for "Detecting if an edge-weighted graph has a triangle of negative total edge weight").

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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