3
$\begingroup$

What are some interesting open or solved-but-hard questions around problems having linear-time solutions? Ala riffle shuffles.

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.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ 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 for a couple of "hard to implement" linear time algorithms. $\endgroup$
    – Marzio De Biasi
    Commented Mar 22, 2013 at 15:01
  • 2
    $\begingroup$ What is "weak" (or, for that matter, "strong") linear time? $\endgroup$
    – Joshua Grochow
    Commented Mar 22, 2013 at 15:51
  • 1
    $\begingroup$ @MarzioDeBiasi: Your comment should be an answer! $\endgroup$
    – Jeffε
    Commented Mar 22, 2013 at 17:57
  • 1
    $\begingroup$ So, are you interested in algorithms (described in a random-access model of computation) or complexity results (framed in terms of Turing machines)? $\endgroup$
    – Jeffε
    Commented Mar 22, 2013 at 18:44
  • $\begingroup$ Yeah, Marzio's comment answer is plenty to keep me chugging along here, thank you! $\endgroup$
    – Jeff Burdges
    Commented Mar 23, 2013 at 18:02

0

Reset to default

Your Answer

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