<p>I believe that the &quot;state of the art&quot; 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 <em>fine-grained complexity</em> gives you many problems that are in P but require superlinear time under some assumptions. In this <a href="https://people.csail.mit.edu/virgi/eccentri.pdf" rel="nofollow noreferrer">survey of fine-grained complexity</a> there are several such problems and some of them are in NL (for example there is an obvious NL algorithm for &quot;Detecting if an edge-weighted graph has a triangle of negative total edge weight&quot;).</p>

CC BY-SA 4.0
2022-11-04T19:43:00.730Z
2022-11-04T19:43:00.730Z
Lê Thành Dũng 'Tito' Nguyễn
<p>It is a well-known fact that $ \mathsf{NL} = \cup_{k&gt;0} \mathsf{2NFA[k]} $, where $ \mathsf{2NFA[k]} $ is the class of languages recognized by two-way nondeterministic finite automata with $ k&gt;0 $ input heads, shortly 2nfa(k).</p>

<p>I have two but similar questions:</p>

<p>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?</p>

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

CC BY-SA 3.0
2012-07-25T13:50:27.127Z
I think both your questions are the same question. Do you have a reason for them being different, or are you just unsure?
Luke Mathieson
CC BY-SA 3.0
2012-07-25T14:00:56.610Z
@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.
Abuzer Yakaryilmaz
CC BY-SA 3.0
2012-07-25T14:17:40.810Z
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.
Luke Mathieson
CC BY-SA 3.0
2012-07-25T14:25:35.893Z
@LukeMathieson: Yes!
Abuzer Yakaryilmaz
CC BY-SA 3.0
2012-07-26T13:19:45.327Z
In the first question, you wrote "requiring super-linear time," but in which computational model?
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-26T13:47:21.923Z
@TsuyoshiIto: Thank you for your comment. I edited the text.
Abuzer Yakaryilmaz
<cc.complexity-theory><reference-request><automata-theory><logspace>
A super-linear time problem in NL
Abuzer Yakaryilmaz
# A super-linear time problem in NL

(Asked by: username_0 on 2012-07-25)

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?

**Tags:** cc.complexity-theory, reference-request, automata-theory, logspace

> **Comments:**
> **username_1**: I think both your questions are the same question. Do you have a reason for them being different, or are you just unsure?  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_0**: @LukeMathieson: Yes!  
> **username_2**: In the first question, you wrote "requiring super-linear time," but in which computational model?  
> **username_0**: @TsuyoshiIto: Thank you for your comment. I edited the text.  

---

## 1 answers

### Answer by username_3 on 2022-11-04. Score: 4

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](https://people.csail.mit.edu/virgi/eccentri.pdf) 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").


---

