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.

  • 3
    $\begingroup$ Are you looking for problems with one specific $p$, say $p=3$, or for a family of natural problems that can be solved in $n^p$ time but not in $n^{p-1}$ time for some parameter $p$? If you are fine with problems that are conjectured to have such running times, then you should look for work in fine-grained complexity. This area deals with (conditional) lower bounds for problems in P. $\endgroup$ – Christian Komusiewicz Feb 4 '20 at 8:26
  • 1
    $\begingroup$ I'm interested in both. Thank you for the intel. If you have a specific problem then i'm interested. $\endgroup$ – PMercier Feb 4 '20 at 10:00
  • $\begingroup$ I recently stumbled upon a paper that lists P-complete problems. It's possible that some of these problems might have polynomial time lower bounds by a reduction from time bounded Turing machine simulation. The paper is "A Compendium of Problems Complete for P" by Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo: citeseerx.ist.psu.edu/viewdoc/summary?doi= $\endgroup$ – Michael Wehar Apr 8 '20 at 16:55

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:

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!

  • 1
    $\begingroup$ Here's another post that might be relevant: cstheory.stackexchange.com/questions/33063/… $\endgroup$ – Michael Wehar Feb 4 '20 at 17:15
  • 1
    $\begingroup$ Thank you for your detailled answer. I've read the first paper and the beginning of the second. It seems in both cases they use a simulation of TM to prove their result and then conclude by the time hierarchy theorem which is what i'm trying to avoid. I should have been clearer in my way of stating it in my original post, i'll edit it. $\endgroup$ – PMercier Feb 5 '20 at 2:07
  • 1
    $\begingroup$ @PMercier Thank you very much for the follow-up! That makes sense. Well it could be an ugly thought, but it seems possible that for every problem $X \in DTIME(n^p) - DTIME(n^{p-1})$ we have that every problem in $DTIME(n^{p-1})$ has a fine-grained reduction to $X$. In other words, maybe reduction from Turing machine simulation is the way to show lower bounds. $\endgroup$ – Michael Wehar Feb 5 '20 at 3:49
  • $\begingroup$ @PMercier I posted a question about this: cstheory.stackexchange.com/questions/46292/… $\endgroup$ – Michael Wehar Feb 5 '20 at 4:46
  • 1
    $\begingroup$ I also thought about this possibility but it intuitively seems ludicrous. If I come up with a better justification I'll make sure to answer your post. I am very interested in an answer to this question. $\endgroup$ – PMercier Feb 5 '20 at 5:06

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.
  • $\begingroup$ I am accepting this answer because as of the current state of research it seems that standalone conjecture is the state of the art. $\endgroup$ – PMercier Feb 10 '20 at 3:07
  • $\begingroup$ Thank you for sharing! I actually hadn't known about the paper "How hard are n^2-hard problems?" but was aware of their theorem. It really helps to have a more complete history. $\endgroup$ – Michael Wehar Feb 10 '20 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.