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?

  • $\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 Jul 25 '12 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 Jul 25 '12 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 Jul 25 '12 at 14:17
  • $\begingroup$ @LukeMathieson: Yes! $\endgroup$ – Abuzer Yakaryilmaz Jul 25 '12 at 14:25
  • 1
    $\begingroup$ In the first question, you wrote "requiring super-linear time," but in which computational model? $\endgroup$ – Tsuyoshi Ito Jul 26 '12 at 13:19

Your Answer

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

Browse other questions tagged or ask your own question.