<p>The answer to the question is yes, assuming that (for all large <span class="math-container">$k$</span>) <span class="math-container">$k$</span>-SUM is not in <span class="math-container">$\text{DTIME}(n^{o(k)})$</span>.</p>
<p>It also follows (by a <a href="https://cs.stackexchange.com/a/2977/4678">result of Patrascu and Williams</a>) that <em>the answer is yes assuming the ETH holds.</em></p>
<p>The proof reuses the classical technique from the classical proof that, if any unary language is NP-hard, then P=NP.</p>
<h3>Definitions</h3>
<ul>
<li><p><strong>The question:</strong> <em>Does there exist <span class="math-container">$k \geq 2$</span> such that there exist problems in <span class="math-container">$\text{DTIME}(n^k) - \text{DTIME}(n^{k-1})$</span> that are not computationally hard for <span class="math-container">$\text{DTIME}(n^{k-1})$</span> under nearly linear-time reductions?</em></p>
</li>
<li><p><strong>The <span class="math-container">$k$</span>-SUM problem:</strong> <em>Given <span class="math-container">$n$</span> integers, are there <span class="math-container">$k$</span> of them that sum to zero?</em></p>
</li>
<li><p><strong>ETH (the Exponential Time Hypothesis):</strong> <em>3-SAT is not in <span class="math-container">$\text{DTIME}(2^{o(n)})$</span>.</em></p>
</li>
</ul>
<h3>Result</h3>
<p><strong>Theorem 1.</strong> <em>Assume that (for all <span class="math-container">$k$</span>), <span class="math-container">$k$</span>-SUM is not in <span class="math-container">$\text{DTIME}(n^{o(k)})$</span>.  Then the answer to the question is yes.</em></p>
<p><em>Proof.</em> We show the contrapositive.  Assume that the answer to the question is no.  As observed in the post, this implies that, for all sufficiently large <span class="math-container">$k$</span>, there is a unary language that is hard for <span class="math-container">$\text{DTIME}(n^k)$</span> under nearly linear-time reductions.  To complete the proof we show the following:</p>
<p><strong>Lemma 1.</strong> <em>Assume that, for some <span class="math-container">$c\ge 1$</span>, for all sufficiently large <span class="math-container">$k$</span>, there is a unary language that is hard for <span class="math-container">$\text{DTIME}(n^k)$</span> under <span class="math-container">$O(n^c)$</span>-time reductions.  Then, for all <span class="math-container">$k$</span>, <span class="math-container">$k$</span>-SUM is in <span class="math-container">$\text{DTIME}(n^{2c+1}) \subseteq \text{DTIME}(n^{o(k)})$</span>.</em></p>
<p><em>Proof.</em> Fix such a <span class="math-container">$c\ge 1$</span> and an arbitrarily large <span class="math-container">$k$</span>. Let <span class="math-container">$L\subseteq 1^*$</span> be the unary language that is hard for <span class="math-container">$\text{DTIME}(n^{k+1})$</span> under <span class="math-container">$O(n^c)$</span>-time reductions.</p>
<p>Define the following generalization of <span class="math-container">$k$</span>-SUM, called <span class="math-container">$k$</span>-SUM'.  The input consists of <span class="math-container">$n$</span> integers, a target <span class="math-container">$t$</span>, and a budget <span class="math-container">$d\le k$</span>.  The question is whether any <span class="math-container">$d$</span> of the given integers sum to <span class="math-container">$t$</span>.</p>
<p>To prove the lemma, we describe an <span class="math-container">$n^{O(c)}$</span>-time algorithm for <span class="math-container">$k$</span>-SUM' (which clearly generalizes <span class="math-container">$k$</span>-SUM).</p>
<p>As <span class="math-container">$k$</span>-SUM' is easily in <span class="math-container">$\text{DTIME}(n^{k+1})$</span>, by definition of <span class="math-container">$L$</span> there is an <span class="math-container">$O(n^c)$</span>-time reduction, say <span class="math-container">$f$</span>, from <span class="math-container">$k$</span>-SUM' to the unary language <span class="math-container">$L$</span>.</p>
<p>We use the classical technique from the proof that, if there is an NP-hard unary language, then P=NP.  Namely, consider the following dynamic-programming algorithm for <span class="math-container">$k$</span>-SUM' (presented here in recursive memoized form):</p>
<ol>
<li><p><strong>input:</strong> <span class="math-container">$k$</span>-SUM' instance <span class="math-container">$I=((x_1, x_2, \ldots, x_n), t, d)$</span></p>
</li>
<li><p>if <span class="math-container">$n=0$</span> or <span class="math-container">$d=0$</span>, return 'true' if <span class="math-container">$t=0$</span> and 'false' otherwise  <em>(base case)</em></p>
</li>
<li><p>compute the reduction <span class="math-container">$f(I) \in 1^*$</span> <em>(the time this takes and <span class="math-container">$|f(I)|$</span> are both <span class="math-container">$O(n^c)$</span>)</em></p>
</li>
<li><p>if we've previously computed the answer for an instance <span class="math-container">$I'$</span> with <span class="math-container">$f(I')=f(I)$</span>, return the same answer for <span class="math-container">$I$</span>.  otherwise:</p>
</li>
<li><p>let <span class="math-container">$I_0$</span> be the <span class="math-container">$k$</span>-SUM' instance <span class="math-container">$((x_1, x_2, \ldots, x_{n-1}), t, d)$</span></p>
</li>
<li><p>let <span class="math-container">$I_1$</span> be the <span class="math-container">$k$</span>-SUM' instance <span class="math-container">$((x_1, x_2, \ldots, x_{n-1}), t-x_n, d-1)$</span></p>
</li>
<li><p>recursively compute the answers for <span class="math-container">$I_0$</span> and <span class="math-container">$I_1$</span></p>
</li>
<li><p>the answer for <span class="math-container">$I$</span> is 'true' iff the answer to <span class="math-container">$I_0$</span> is 'true' or the answer to <span class="math-container">$I_1$</span> is 'true'</p>
</li>
<li><p>memoize the answer for <span class="math-container">$I$</span> in the lookup table, under index <span class="math-container">$f(I)$</span></p>
</li>
<li><p>return the answer for <span class="math-container">$I$</span></p>
</li>
</ol>
<p>The algorithm is correct by standard dynamic-programming reasoning along with the observation that any two <span class="math-container">$k$</span>-SUM' instances that reduce to the same element of <span class="math-container">$L$</span> must have the same answer.</p>
<p>How much time does it take?
For each subproblem (not counting the recursive calls) the time is dominated by the the time to compute <span class="math-container">$f(I)$</span>, which is <span class="math-container">$O(n^c)$</span>.</p>
<p>Each subproblem <span class="math-container">$I'$</span> that arises in the recursion has size <span class="math-container">$O(n)$</span>, so <span class="math-container">$f(I')$</span> is of the form <span class="math-container">$1^m$</span> for <span class="math-container">$m = O(n^c)$</span>.  Thus, the number of &quot;distinct subproblems&quot; (whose answers are not already cached when they arise) is <span class="math-container">$O(n^{c+1})$</span> (we get an extra factor of <span class="math-container">$n$</span> because if a subproblem <span class="math-container">$I$</span> has an ancestor <span class="math-container">$I'$</span> with <span class="math-container">$f(I)=f(I')$</span>, the answer for <span class="math-container">$f(I')$</span> won't be cached when <span class="math-container">$I$</span> is encountered).  It follows that the recursion tree has <span class="math-container">$O(n^{c+1})$</span> nodes, and the total time is <span class="math-container">$O(n^{2c+1})$</span>.  <span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2021-05-28T23:20:22.830Z
Looks very related to https://dl.acm.org/doi/abs/10.1145/181462.181465 who show that if 3SUM is quasi-linear-time hard for quadratic time, then P != NP. In fact, from the same hypothesis, every problem in P can be simulated in quasi-linear time with O(log n) nondeterminism. This in turn would probably refute *some* nondeterministic versions of ETH: by padding, we would get that 2^n time can be simulated with O(n) nondeterminism in 2^(eps n) time for all eps > 0.
Ryan Williams
CC BY-SA 4.0
2021-05-29T02:00:26.467Z
@RyanWilliams, interesting.. That does sound like a similar (probably stronger) result.
Neal Young
CC BY-SA 4.0
2021-05-18T02:46:29.177Z
2021-05-19T00:39:10.353Z
2021-05-19T00:39:10.353Z
Neal Young
<p>You might have the right idea. Let <span class="math-container">$X'$</span> be a tally language (only composed of strings of 1-s) in <span class="math-container">$DTIME(n^k) -DTIME(n^{k-1})$</span>. It is routine to construct such a set using the classical idea from the time hierarchy theorem. Alternatively one can use the construction you gave to construct <span class="math-container">$X'$</span>. <span class="math-container">$X'$</span> is <span class="math-container">$DTIME(n^{k-1})$</span> hard by assumption. <span class="math-container">$X' \in DTIME(n)_{/O(1)}$</span> because it is a tally language (<span class="math-container">$DTIME(n)_{/O(1)}$</span> denotes the language recognizable in linear time with a constant number of bits of advice).</p>

<p>Since, on the other hand, <span class="math-container">$X'$</span> is <span class="math-container">$DTIME(n^{k-1})$</span> hard (for quasi linear reductions) we have that <span class="math-container">$DTIME(n^{k-1}) \subset DTIME(n)_{/O(n)}$</span>.</p>

<p>Also, it is known that <span class="math-container">$\forall i, DTIME(n^{i}) \nsubseteq DTIME(n^{i-1})_{/o(n)}$</span> (this is proven by diagonalization).</p>

<p>We seem close to obtaining a contradiction.  Let's continue thinking about this...</p>

<p>Sidenote 1 : I believe this can be related to the proof that there cannot be any tally <span class="math-container">$NP-complete$</span> set (assuming <span class="math-container">$P \neq NP$</span>).</p>

<p>Sidenote 2: It's unclear if this argument can be extended to prove that sparse sets cannot be <span class="math-container">$DTIME(n{^k})$</span> complete.</p>

CC BY-SA 4.0
2020-02-05T05:52:16.517Z
Can your argument be generalized to show that: there are problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under $n^{k-1-\varepsilon}$-time reductions for all $\varepsilon > 0$?
Michael Wehar
CC BY-SA 4.0
2020-02-05T06:09:50.523Z
I'm a little uncertain about your statement that $DTIME(n^{k-1}) \subset DTIME(n)_{/O(1)}$.  I thought we would get $DTIME(n^{k-1}) \subset DTIME(n^{1 + o(1)})_{/O(n^{1 + o(1)})}$ because each instance could be reduced to any of $n^{1 + o(1)}$ unary strings.
Michael Wehar
CC BY-SA 4.0
2020-02-05T06:11:18.343Z
Also, do you happen to have a reference for: $\forall i, DTIME(n^{i}) \nsubseteq DTIME(n^{i-1})_{/o(n)}$ ?  Thank you again!  :)
Michael Wehar
CC BY-SA 4.0
2020-02-05T06:22:38.227Z
You are right, there is a mistake where you pointed out. Unfortunately we currently don't even know if $P \subset SIZE(O(n))$ so we can't easily salvage the proof. I will post again if i have a fruitful idea.
ULechine
CC BY-SA 4.0
2020-02-05T06:28:36.023Z
I can't find the paper in which I read this result. I may try to give you the idea here. You start a normal diagonalization against small-advice taking machines and for the advice you use the $a(n)$ first bits of the input, where $a(n)$ is the size of the advice. There is a $x \in \{ 0 ;1 \}^n$ such that the first $a(n)$ bits of $x$ coincide with the actual advice the machine should get on inputs of size n. You can then conclude.
ULechine
CC BY-SA 4.0
2020-02-05T18:25:17.440Z
Thank you very much for the comments!  I think that I'm on the same page now.
Michael Wehar
CC BY-SA 4.0
2020-02-10T02:27:29.640Z
This [answer](https://cstheory.stackexchange.com/a/1287/55419) from another post yields very interesting elements to your question. Although it does not answer it unconditionnaly. (I wish I could comment directly under your post but I don't have enough points)
ULechine
CC BY-SA 4.0
2020-02-05T05:41:26.927Z
2020-02-05T17:43:44.130Z
2020-02-05T17:43:44.130Z
ULechine
<p><strong>Background</strong></p>

<p>It can be challenging to find computational problems that are solvable in <span class="math-container">$DTIME(n^k) - DTIME(n^{k-1})$</span> where <span class="math-container">$k \geq 2$</span>.</p>

<p>Although some natural problems are known to exist, many of them are in someway equivalent to simulating Turing machines or the lower bound result is heavily dependent on the machine model.</p>

<p>See this question for more details: <a href="https://cstheory.stackexchange.com/questions/46284/problem-in-deterministic-time-np-and-not-lower">Problem in deterministic time $n^p$ and not lower</a></p>

<hr>

<p><strong>Question</strong></p>

<p>Does there exist <span class="math-container">$k \geq 2$</span> such that there exist problems in <span class="math-container">$DTIME(n^k) - DTIME(n^{k-1})$</span> that are not computationally hard for <span class="math-container">$DTIME(n^{k-1})$</span> under nearly linear time reductions?</p>

<p><strong>Update:</strong> As pointed out by @NealYoung in the comments, when <span class="math-container">$k=2$</span>, no such problems exist.  Also, for the computational model, let's go with multitape Turing machine.</p>

<hr>

<p><strong>Why does it matter?</strong></p>

<p>I suspect that if the answer is false (meaning that no such problems exist), then all polynomial time problems have non-uniform nearly linear size circuits.</p>

<hr>

<p><strong>Let me try to explain.</strong></p>

<p>Let <span class="math-container">$k \geq 2$</span> be given.</p>

<p>Suppose for a minute that every problem in <span class="math-container">$DTIME(n^k) - DTIME(n^{k-1})$</span> is hard for <span class="math-container">$DTIME(n^{k-1})$</span> under nearly linear time reductions.</p>

<p>Next, consider a problem <span class="math-container">$X$</span> that is complete for <span class="math-container">$DTIME(2^{k \cdot n})$</span> (such as the problem of simulating a <span class="math-container">$2^{k \cdot n}$</span>-time bounded Turing machine on an input).  By the time hierarchy theorem, this problem cannot be solved in much less than <span class="math-container">$2^{k \cdot n}$</span> time.</p>

<p>Then, convert this problem <span class="math-container">$X$</span> from binary inputs to unary inputs to get a problem <span class="math-container">$X'$</span>.  We have that <span class="math-container">$X' \in DTIME(n^k) - DTIME(n^{k-1})$</span>.  By the assumption, it follows that <span class="math-container">$X'$</span> is hard for <span class="math-container">$DTIME(n^{k-1})$</span> under nearly linear time reductions.</p>

<p>Finally, we can build small non-uniform circuits for <span class="math-container">$X'$</span> because there are so few possible unary input strings.  Also, we can build a small circuit for any nearly linear time reduction.  Combining these together, we get small circuits for all problems in <span class="math-container">$DTIME(n^{k-1})$</span>.</p>

<p>Maybe we can get a contradiction based on some known circuit lower bounds?  Or, there could even be relativized results that come into play.  Any thoughts are greatly appreciated.  Thank you!</p>

CC BY-SA 4.0
2020-02-05T04:48:03.010Z
Note: This question is essentially asking whether there exist problems with unconditional time complexity lower bounds that are not equivalent to simulating Turing machines.
Michael Wehar
CC BY-SA 4.0
2020-02-05T05:06:43.423Z
More thoughts: If this were false, it would mean that lower bound proofs are in a sense constructive.  If there is a lower bound, then there must exist a reduction that acts as a witness to the lower bound.
Michael Wehar
CC BY-SA 4.0
2020-02-07T18:56:40.027Z
The following is a related question that might be easier to answer. Is every problem with an $n^k$-time lower bound hard for $DTIME(n^k)$ under nearly linear time reductions?
Michael Wehar
CC BY-SA 4.0
2020-02-08T01:34:10.690Z
Here is a trivial observation for the main question for the case $k=2$.  Any non-trivial problem $B$ is hard for $\text{DTIME}(n)$ under linear-time reductions: for any $A\in\text{DTIME}(n)$, the reduction can simply solve the instance of $A$ and produce one of two appropriate instances (yes or no) of $B$.  So the answer to your questions as phrased ("*for every $k\ge 2$*") is false simply because it fails for this trivial reason for $k=2$.  Unless I'm missing something?
Neal Young
CC BY-SA 4.0
2020-02-08T01:40:44.283Z
Also, in defining "*nearly linear-time reduction*", what is your computational model?  If you had in mind a single-tape TM, note that any language defined by a single-tape deterministic TM that runs in $o(n\log n)$ time must be regular.  So some care is needed there.
Neal Young
CC BY-SA 4.0
2020-02-09T01:15:27.043Z
@NealYoung Thank you very much for your helpful comments!  When I initially asked the question, I fumbled and wasn't sure if I should put any or every.  But, now I'm confident, I want any.  I will edit the question and cite your comment.
Michael Wehar
CC BY-SA 4.0
2020-02-09T01:30:13.967Z
@NealYoung Again, I wasn't sure if I should pick multitape Turing machine or RAM machine.  I think we should go with multi-tape Turing machine.
Michael Wehar
<cc.complexity-theory><circuit-complexity><time-complexity><lower-bounds><structural-complexity>
Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?
Michael Wehar
# Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?

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

**Background**

It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$.

Although some natural problems are known to exist, many of them are in someway equivalent to simulating Turing machines or the lower bound result is heavily dependent on the machine model.

See this question for more details: [Problem in deterministic time $n^p$ and not lower](https://cstheory.stackexchange.com/questions/46284/problem-in-deterministic-time-np-and-not-lower)

---

**Question**

Does there exist $k \geq 2$ such that there exist problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not computationally hard for $DTIME(n^{k-1})$ under nearly linear time reductions?

**Update:** As pointed out by @NealYoung in the comments, when $k=2$, no such problems exist. Also, for the computational model, let's go with multitape Turing machine.

---

**Why does it matter?**

I suspect that if the answer is false (meaning that no such problems exist), then all polynomial time problems have non-uniform nearly linear size circuits.

---

**Let me try to explain.**

Let $k \geq 2$ be given.

Suppose for a minute that every problem in $DTIME(n^k) - DTIME(n^{k-1})$ is hard for $DTIME(n^{k-1})$ under nearly linear time reductions.

Next, consider a problem $X$ that is complete for $DTIME(2^{k \cdot n})$ (such as the problem of simulating a $2^{k \cdot n}$-time bounded Turing machine on an input). By the time hierarchy theorem, this problem cannot be solved in much less than $2^{k \cdot n}$ time.

Then, convert this problem $X$ from binary inputs to unary inputs to get a problem $X'$. We have that $X' \in DTIME(n^k) - DTIME(n^{k-1})$. By the assumption, it follows that $X'$ is hard for $DTIME(n^{k-1})$ under nearly linear time reductions.

Finally, we can build small non-uniform circuits for $X'$ because there are so few possible unary input strings. Also, we can build a small circuit for any nearly linear time reduction. Combining these together, we get small circuits for all problems in $DTIME(n^{k-1})$.

Maybe we can get a contradiction based on some known circuit lower bounds? Or, there could even be relativized results that come into play. Any thoughts are greatly appreciated. Thank you!

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

> **Comments:**
> **username_0**: Note: This question is essentially asking whether there exist problems with unconditional time complexity lower bounds that are not equivalent to simulating Turing machines.  
> **username_0**: More thoughts: If this were false, it would mean that lower bound proofs are in a sense constructive.  If there is a lower bound, then there must exist a reduction that acts as a witness to the lower bound.  
> **username_0**: The following is a related question that might be easier to answer. Is every problem with an $n^k$-time lower bound hard for $DTIME(n^k)$ under nearly linear time reductions?  
> **username_1**: Here is a trivial observation for the main question for the case $k=2$.  Any non-trivial problem $B$ is hard for $\text{DTIME}(n)$ under linear-time reductions: for any $A\in\text{DTIME}(n)$, the reduction can simply solve the instance of $A$ and produce one of two appropriate instances (yes or no) of $B$.  So the answer to your questions as phrased ("*for every $k\ge 2$*") is false simply because it fails for this trivial reason for $k=2$.  Unless I'm missing something?  
> **username_1**: Also, in defining "*nearly linear-time reduction*", what is your computational model?  If you had in mind a single-tape TM, note that any language defined by a single-tape deterministic TM that runs in $o(n\log n)$ time must be regular.  So some care is needed there.  
> **username_0**: @NealYoung Thank you very much for your helpful comments!  When I initially asked the question, I fumbled and wasn't sure if I should put any or every.  But, now I'm confident, I want any.  I will edit the question and cite your comment.  
> **username_0**: @NealYoung Again, I wasn't sure if I should pick multitape Turing machine or RAM machine.  I think we should go with multi-tape Turing machine.  

---

## 2 answers

### Answer by username_1 on 2021-05-18. Score: 2

The answer to the question is yes, assuming that (for all large $k$) $k$-SUM is not in $\text{DTIME}(n^{o(k)})$.

It also follows (by a [result of Patrascu and Williams](https://cs.stackexchange.com/a/2977/4678)) that *the answer is yes assuming the ETH holds.*

The proof reuses the classical technique from the classical proof that, if any unary language is NP-hard, then P=NP.

### Definitions

* **The question:** *Does there exist $k \geq 2$ such that there exist problems in $\text{DTIME}(n^k) - \text{DTIME}(n^{k-1})$ that are not computationally hard for $\text{DTIME}(n^{k-1})$ under nearly linear-time reductions?*
* **The $k$-SUM problem:** *Given $n$ integers, are there $k$ of them that sum to zero?*
* **ETH (the Exponential Time Hypothesis):** *3-SAT is not in $\text{DTIME}(2^{o(n)})$.*

### Result

**Theorem 1.** *Assume that (for all $k$), $k$-SUM is not in $\text{DTIME}(n^{o(k)})$. Then the answer to the question is yes.*

*Proof.* We show the contrapositive. Assume that the answer to the question is no. As observed in the post, this implies that, for all sufficiently large $k$, there is a unary language that is hard for $\text{DTIME}(n^k)$ under nearly linear-time reductions. To complete the proof we show the following:

**Lemma 1.** *Assume that, for some $c\ge 1$, for all sufficiently large $k$, there is a unary language that is hard for $\text{DTIME}(n^k)$ under $O(n^c)$-time reductions. Then, for all $k$, $k$-SUM is in $\text{DTIME}(n^{2c+1}) \subseteq \text{DTIME}(n^{o(k)})$.*

*Proof.* Fix such a $c\ge 1$ and an arbitrarily large $k$. Let $L\subseteq 1^\*$ be the unary language that is hard for $\text{DTIME}(n^{k+1})$ under $O(n^c)$-time reductions.

Define the following generalization of $k$-SUM, called $k$-SUM'. The input consists of $n$ integers, a target $t$, and a budget $d\le k$. The question is whether any $d$ of the given integers sum to $t$.

To prove the lemma, we describe an $n^{O(c)}$-time algorithm for $k$-SUM' (which clearly generalizes $k$-SUM).

As $k$-SUM' is easily in $\text{DTIME}(n^{k+1})$, by definition of $L$ there is an $O(n^c)$-time reduction, say $f$, from $k$-SUM' to the unary language $L$.

We use the classical technique from the proof that, if there is an NP-hard unary language, then P=NP. Namely, consider the following dynamic-programming algorithm for $k$-SUM' (presented here in recursive memoized form):

1. **input:** $k$-SUM' instance $I=((x\_1, x\_2, \ldots, x\_n), t, d)$
2. if $n=0$ or $d=0$, return 'true' if $t=0$ and 'false' otherwise *(base case)*
3. compute the reduction $f(I) \in 1^\*$ *(the time this takes and $|f(I)|$ are both $O(n^c)$)*
4. if we've previously computed the answer for an instance $I'$ with $f(I')=f(I)$, return the same answer for $I$. otherwise:
5. let $I\_0$ be the $k$-SUM' instance $((x\_1, x\_2, \ldots, x\_{n-1}), t, d)$
6. let $I\_1$ be the $k$-SUM' instance $((x\_1, x\_2, \ldots, x\_{n-1}), t-x\_n, d-1)$
7. recursively compute the answers for $I\_0$ and $I\_1$
8. the answer for $I$ is 'true' iff the answer to $I\_0$ is 'true' or the answer to $I\_1$ is 'true'
9. memoize the answer for $I$ in the lookup table, under index $f(I)$
10. return the answer for $I$

The algorithm is correct by standard dynamic-programming reasoning along with the observation that any two $k$-SUM' instances that reduce to the same element of $L$ must have the same answer.

How much time does it take?
For each subproblem (not counting the recursive calls) the time is dominated by the the time to compute $f(I)$, which is $O(n^c)$.

Each subproblem $I'$ that arises in the recursion has size $O(n)$, so $f(I')$ is of the form $1^m$ for $m = O(n^c)$. Thus, the number of "distinct subproblems" (whose answers are not already cached when they arise) is $O(n^{c+1})$ (we get an extra factor of $n$ because if a subproblem $I$ has an ancestor $I'$ with $f(I)=f(I')$, the answer for $f(I')$ won't be cached when $I$ is encountered). It follows that the recursion tree has $O(n^{c+1})$ nodes, and the total time is $O(n^{2c+1})$. $~~~\Box$

> **Comments:**
> **username_2**: Looks very related to https://dl.acm.org/doi/abs/10.1145/181462.181465 who show that if 3SUM is quasi-linear-time hard for quadratic time, then P != NP. In fact, from the same hypothesis, every problem in P can be simulated in quasi-linear time with O(log n) nondeterminism. This in turn would probably refute *some* nondeterministic versions of ETH: by padding, we would get that 2^n time can be simulated with O(n) nondeterminism in 2^(eps n) time for all eps > 0.  
> **username_1**: @RyanWilliams, interesting.. That does sound like a similar (probably stronger) result.  

---

### Answer by username_3 on 2020-02-05. Score: 1

You might have the right idea. Let $X'$ be a tally language (only composed of strings of 1-s) in $DTIME(n^k) -DTIME(n^{k-1})$. It is routine to construct such a set using the classical idea from the time hierarchy theorem. Alternatively one can use the construction you gave to construct $X'$. $X'$ is $DTIME(n^{k-1})$ hard by assumption. $X' \in DTIME(n)\_{/O(1)}$ because it is a tally language ($DTIME(n)\_{/O(1)}$ denotes the language recognizable in linear time with a constant number of bits of advice).

Since, on the other hand, $X'$ is $DTIME(n^{k-1})$ hard (for quasi linear reductions) we have that $DTIME(n^{k-1}) \subset DTIME(n)\_{/O(n)}$.

Also, it is known that $\forall i, DTIME(n^{i}) \nsubseteq DTIME(n^{i-1})\_{/o(n)}$ (this is proven by diagonalization).

We seem close to obtaining a contradiction. Let's continue thinking about this...

Sidenote 1 : I believe this can be related to the proof that there cannot be any tally $NP-complete$ set (assuming $P \neq NP$).

Sidenote 2: It's unclear if this argument can be extended to prove that sparse sets cannot be $DTIME(n{^k})$ complete.

> **Comments:**
> **username_0**: Can your argument be generalized to show that: there are problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under $n^{k-1-\varepsilon}$-time reductions for all $\varepsilon > 0$?  
> **username_0**: I'm a little uncertain about your statement that $DTIME(n^{k-1}) \subset DTIME(n)_{/O(1)}$.  I thought we would get $DTIME(n^{k-1}) \subset DTIME(n^{1 + o(1)})_{/O(n^{1 + o(1)})}$ because each instance could be reduced to any of $n^{1 + o(1)}$ unary strings.  
> **username_0**: Also, do you happen to have a reference for: $\forall i, DTIME(n^{i}) \nsubseteq DTIME(n^{i-1})_{/o(n)}$ ?  Thank you again!  :)  
> **username_3**: You are right, there is a mistake where you pointed out. Unfortunately we currently don't even know if $P \subset SIZE(O(n))$ so we can't easily salvage the proof. I will post again if i have a fruitful idea.  
> **username_3**: I can't find the paper in which I read this result. I may try to give you the idea here. You start a normal diagonalization against small-advice taking machines and for the advice you use the $a(n)$ first bits of the input, where $a(n)$ is the size of the advice. There is a $x \in \{ 0 ;1 \}^n$ such that the first $a(n)$ bits of $x$ coincide with the actual advice the machine should get on inputs of size n. You can then conclude.  
> **username_0**: Thank you very much for the comments!  I think that I'm on the same page now.  
> **username_3**: This [answer](https://cstheory.stackexchange.com/a/1287/55419) from another post yields very interesting elements to your question. Although it does not answer it unconditionnaly. (I wish I could comment directly under your post but I don't have enough points)  

---

