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?

Question

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

---

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!

Answer 1

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) 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$

Answer 2

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.