<p>What are some interesting open or solved-but-hard questions around problems having linear-time solutions?  Ala <a href="https://cstheory.stackexchange.com/questions/13943/linear-time-in-place-riffle-shuffle-algorithm">riffle shuffles</a>.</p>

<p>I'm especially curious about problems which people believe to be linear-time but for which either no linear-time algorithm is known or for which finding one proved difficult. </p>

<p>As a technical matter, I'm perhaps most interested in weak-linear-time on a single-tape nondeterministic machine, but other linear-time models are still interesting, ala deterministic or multi-tape models.  I'm aware that strong-linear-time on a single tape nondeterministic machine is regular, hence linear-time on a single-tape deterministic machine is regular too. </p>

CC BY-SA 3.0
2013-03-22T15:01:20.067Z
[Minimum Spanning Tree](http://en.wikipedia.org/wiki/Minimum_spanning_tree) algorithm. From Wikipedia: *... Whether the problem can be solved deterministically in linear time by a comparison-based algorithm remains an open question ...*. See also this [question](http://cstheory.stackexchange.com/questions/4491/powerful-algorithms-too-complex-to-implement) for a couple of "hard to implement" linear time algorithms.
Marzio De Biasi
CC BY-SA 3.0
2013-03-22T15:51:21.603Z
What is "weak" (or, for that matter, "strong") linear time?
Joshua Grochow
CC BY-SA 3.0
2013-03-22T17:57:23.507Z
@MarzioDeBiasi: Your comment should be an answer!
Jeffε
CC BY-SA 3.0
2013-03-22T18:44:08.013Z
So, are you interested in algorithms (described in a random-access model of computation) or complexity results (framed in terms of Turing machines)?
Jeffε
CC BY-SA 3.0
2013-03-23T18:02:55.240Z
Yeah, Marzio's comment answer is plenty to keep me chugging along here, thank you!
Jeff Burdges
<cc.complexity-theory><ds.algorithms><time-complexity><nondeterminism><time-hierarchy>
Open questions about linear-time
Jeff Burdges
# Open questions about linear-time

(Asked by: username_0 on 2013-03-22)

What are some interesting open or solved-but-hard questions around problems having linear-time solutions? Ala [riffle shuffles](https://cstheory.stackexchange.com/questions/13943/linear-time-in-place-riffle-shuffle-algorithm).

I'm especially curious about problems which people believe to be linear-time but for which either no linear-time algorithm is known or for which finding one proved difficult.

As a technical matter, I'm perhaps most interested in weak-linear-time on a single-tape nondeterministic machine, but other linear-time models are still interesting, ala deterministic or multi-tape models. I'm aware that strong-linear-time on a single tape nondeterministic machine is regular, hence linear-time on a single-tape deterministic machine is regular too.

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity, nondeterminism, time-hierarchy
> **Comments:**
> **username_1**: [Minimum Spanning Tree](http://en.wikipedia.org/wiki/Minimum_spanning_tree) algorithm. From Wikipedia: *... Whether the problem can be solved deterministically in linear time by a comparison-based algorithm remains an open question ...*. See also this [question](http://cstheory.stackexchange.com/questions/4491/powerful-algorithms-too-complex-to-implement) for a couple of "hard to implement" linear time algorithms.  
> **username_2**: What is "weak" (or, for that matter, "strong") linear time?  
> **username_3**: @MarzioDeBiasi: Your comment should be an answer!  
> **username_3**: So, are you interested in algorithms (described in a random-access model of computation) or complexity results (framed in terms of Turing machines)?  
> **username_0**: Yeah, Marzio's comment answer is plenty to keep me chugging along here, thank you!  

---

## 0 answers

