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.