Problem in deterministic time $n^p$ and not lower I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable).

I'm interested in a concrete example, languages of the type " Given $M,x,1^n$ is M printing 1 on input x in less than $n^p$ steps" is known not to belong in $DTIME(n^{p-1})$ but it's very hard to understand why intrinsically it is not in $DTIME(n^{p-1})$.

To my knowledge it is a big open question to find such an explicit $L$, so I'm fine with languages conjectured to be in such classes.

I'm also interested if you replace deterministic time with space, non deterministic time, or probabilistic time, but it should remain polynomial.

Edit: More generally I'm also trying to avoid problems which can be shown to be equivalent to simulations of TM. Unless the lowerbound does not use this fact.

One example of a problem i'd be interested in could be something like "is this graph planar ?". Unfortunately this problem is known to be solvable in linear time.
For many years researchers have studied pebbling problems and emptiness/reachability problems.  Some of these problems have known unconditional resource lower bounds.

Such a problem $X$ is typically shown to have unconditional time complexity lower bounds by reducing the simulation of an $n^k$-time bounded Turing machine on a given input to an instance of $X$.  The time hierarchy theorem can then be applied to obtain the lower bound.

Here are two examples:


Pebbling games: A. Adachi, S. Iwata, T. Kasai. Some Combinatorial Game Problems Require Omega(n^k) Time. 1984
Intersecting one context-free language with k regular languages OR Intersecting k tree languages:  J. Swernofsky  and  M.  Wehar. On  the  complexity  of  intersecting  regular,  context-free, and tree languages. 2015




It's worth noting that there is a parameterized complexity class called $XP$ which contains parameterized problems that are solvable in $n^{f(k)}$ time.  A parameterized problem $X$ is $XP$-complete if every $XP$ problem is $fpt$-reducible to $X$.  There are a few known $XP$-complete problems.  Each $XP$-complete problem $X$ satisfies the property that there exist unbounded functions $f$ and $g$ such that for every $k$, $k$-$X \in DTIME(n^{f(k)})$ and $k$-$X \notin DTIME(n^{g(k)})$.

There are some parameterized problems $Y$ with finer reductions where we know that there exist $c_1 &gt; 0$ and $c_2 &gt; 0$ such that for all $k$, $k$-$Y \in DTIME(n^{c_1 k})$ and $k$-$Y \notin DTIME(n^{c_2 k})$.

Here is a post about the search for $XP$-complete problems: A list of XP-hard problems



I suspect that we could find a pebbling or reachability problem where it is solvable in cubic time, but not quadratic time (maybe intersecting three tree languages could work?).  However, this would require quite a bit of care and careful investigation of the existing Turing machine simulations.

This is a topic that I am very interested in.  Please always feel welcome to reach out if you would like to discuss this in more detail.  Thank you!