<p>Many answers to this <a href="https://cstheory.stackexchange.com/q/1284/55419">post</a>, 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 (<span class="math-container">$P \neq NP$</span>)</p>

<p>Here is a list of problems taken from this post :</p>

<ul>
<li>The best algorithm for <span class="math-container">$k-SUM$</span> run in time <span class="math-container">$O(n^{\lceil k/2 \rceil})$</span> for even k. The <span class="math-container">$k-SUM$</span> problem is : given a set <span class="math-container">$S$</span> of integers, are there k integers from <span class="math-container">$S$</span> 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 <a href="https://cstheory.stackexchange.com/a/1287/55419">answer</a> for more details.</li>
<li>The <span class="math-container">$k-CLIQUE$</span> problem.</li>
<li>Hopcroft's problem : Given a set of <span class="math-container">$n$</span> points and a set of <span class="math-container">$n$</span> lines in the plane, does any point lie on one of the line? It is believed to take at least <span class="math-container">$O(n^{3/4})$</span> time.</li>
<li>Affine degeneracy problem. Given <span class="math-container">$n$</span> points in <span class="math-container">$d$</span> dimensions. Do <span class="math-container">$d+1$</span> of them lie on a hyperplane of dimension <span class="math-container">$d-1$</span>. Believed to take <span class="math-container">$O(n^d)$</span> time.</li>
</ul>

CC BY-SA 4.0
2020-02-10T03:07:58.467Z
I am accepting this answer because as of the current state of research it seems that standalone conjecture is the state of the art.
ULechine
CC BY-SA 4.0
2020-02-10T09:59:21.553Z
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.
Michael Wehar
CC BY-SA 4.0
2020-02-10T03:06:53.057Z
2020-02-10T09:57:27.487Z
2020-02-10T09:57:27.487Z
ULechine
<p>For many years researchers have studied pebbling problems and emptiness/reachability problems.  Some of these problems have known unconditional resource lower bounds.</p>

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

<p>Here are two examples:</p>

<ul>
<li><p>Pebbling games: <a href="http://dl.acm.org/citation.cfm?id=322433" rel="nofollow noreferrer">A. Adachi, S. Iwata, T. Kasai. Some Combinatorial Game Problems Require Omega(n^k) Time. 1984</a></p></li>
<li><p>Intersecting one context-free language with k regular languages OR Intersecting k tree languages:  <a href="http://michaelwehar.com/documents/LBL_Equivalence.pdf" rel="nofollow noreferrer">J. Swernofsky  and  M.  Wehar. On  the  complexity  of  intersecting  regular,  context-free, and tree languages. 2015</a></p></li>
</ul>

<hr>

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

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

<p>Here is a post about the search for <span class="math-container">$XP$</span>-complete problems: <a href="https://cstheory.stackexchange.com/questions/37997/a-list-of-xp-hard-problems">A list of XP-hard problems</a></p>

<hr>

<p>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.</p>

<p>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!</p>

CC BY-SA 4.0
2020-02-04T17:15:05.630Z
Here's another post that might be relevant: https://cstheory.stackexchange.com/questions/33063/are-there-more-polynomial-time-problems-with-complexity-lower-bounds
Michael Wehar
CC BY-SA 4.0
2020-02-05T02:07:22.027Z
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.
ULechine
CC BY-SA 4.0
2020-02-05T03:49:25.397Z
@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.
Michael Wehar
CC BY-SA 4.0
2020-02-05T04:46:06.427Z
@PMercier I posted a question about this: https://cstheory.stackexchange.com/questions/46292/are-there-problems-in-dtimenk-dtimenk-1-that-are-not-hard-for-dtime
Michael Wehar
CC BY-SA 4.0
2020-02-05T05:06:07.050Z
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.
ULechine
CC BY-SA 4.0
2020-02-05T05:08:47.597Z
@PMercier Awesome!  I think it might be feasible for us to show a contradiction assuming the "ludicrous" assumption.  If we can, then we've shown that the kinds of problems you're looking for at least exist.  :)
Michael Wehar
CC BY-SA 4.0
2020-02-04T17:12:51.033Z
2020-02-04T17:46:50.840Z
2020-02-04T17:46:50.840Z
Michael Wehar
<p>I'm looking for any language <span class="math-container">$L$</span> candiate to be in <span class="math-container">$DTIME(n^p) -DTIME(n^{p-1})$</span> (it takes at least <span class="math-container">$n^{p-1}$</span> steps to determine if an input is in L with a 2-tape <span class="math-container">$TM$</span>, but L is polynomially solvable).</p>

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

<p>To my knowledge it is a big open question to find such an explicit <span class="math-container">$L$</span>, so I'm fine with languages conjectured to be in such classes.</p>

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

<p><strong>Edit:</strong> 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.</p>

<p>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.</p>

CC BY-SA 4.0
2020-02-04T08:26:44.633Z
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.
Christian Komusiewicz
CC BY-SA 4.0
2020-02-04T10:00:02.290Z
I'm interested in both. Thank you for the intel. If you have a specific problem then i'm interested.
ULechine
CC BY-SA 4.0
2020-04-08T16:55:23.973Z
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: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.2644
Michael Wehar
<cc.complexity-theory><complexity-classes><time-complexity><lower-bounds>
Problem in deterministic time $n^p$ and not lower
ULechine
# Problem in deterministic time $n^p$ and not lower

(Asked by: username_0 on 2020-02-04)

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.

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, lower-bounds

> **Comments:**
> **username_1**: 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.  
> **username_0**: I'm interested in both. Thank you for the intel. If you have a specific problem then i'm interested.  
> **username_2**: 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: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.2644  

---

## 2 answers

### Answer by username_0 on 2020-02-10. Score: 1 | Accepted answer

Many answers to this [post](https://cstheory.stackexchange.com/q/1284/55419), 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](https://cstheory.stackexchange.com/a/1287/55419) 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.

> **Comments:**
> **username_0**: I am accepting this answer because as of the current state of research it seems that standalone conjecture is the state of the art.  
> **username_2**: 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.  

---

### Answer by username_2 on 2020-02-04. Score: 4

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](http://dl.acm.org/citation.cfm?id=322433)
* 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](http://michaelwehar.com/documents/LBL_Equivalence.pdf)

---

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](https://cstheory.stackexchange.com/questions/37997/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!

> **Comments:**
> **username_2**: Here's another post that might be relevant: https://cstheory.stackexchange.com/questions/33063/are-there-more-polynomial-time-problems-with-complexity-lower-bounds  
> **username_0**: 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.  
> **username_2**: @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.  
> **username_2**: @PMercier I posted a question about this: https://cstheory.stackexchange.com/questions/46292/are-there-problems-in-dtimenk-dtimenk-1-that-are-not-hard-for-dtime  
> **username_0**: 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.  
> **username_2**: @PMercier Awesome!  I think it might be feasible for us to show a contradiction assuming the "ludicrous" assumption.  If we can, then we've shown that the kinds of problems you're looking for at least exist.  :)  

---

