Problem in deterministic time $n^p$ and not lower

Question

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.

Answer 1

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 > 0$ and $c_2 > 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!

Answer 2

Many answers to this post, are also answer to this one, although the original question is different. All of the answers to this post are only conjectures though, it even seems there are standalone conjectures, i.e. they don't seem to rely on the usual bigger conjectures ($P \neq NP$)

Here is a list of problems taken from this post :

• The best algorithm for $k-SUM$ run in time $O(n^{\lceil k/2 \rceil})$ for even k. The $k-SUM$ problem is : given a set $S$ of integers, are there k integers from $S$ which sum up to 0. Moreover, it seems likely that any lower bound on this problem can't be derived from the time hierarchy theorem, which is what the post asked for. Read this answer for more details.
• The $k-CLIQUE$ problem.
• Hopcroft's problem : Given a set of $n$ points and a set of $n$ lines in the plane, does any point lie on one of the line? It is believed to take at least $O(n^{3/4})$ time.
• Affine degeneracy problem. Given $n$ points in $d$ dimensions. Do $d+1$ of them lie on a hyperplane of dimension $d-1$. Believed to take $O(n^d)$ time.