5
$\begingroup$

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!

$\endgroup$
7
  • $\begingroup$ Note: This question is essentially asking whether there exist problems with unconditional time complexity lower bounds that are not equivalent to simulating Turing machines. $\endgroup$ Feb 5 '20 at 4:48
  • $\begingroup$ 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. $\endgroup$ Feb 5 '20 at 5:06
  • $\begingroup$ 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? $\endgroup$ Feb 7 '20 at 18:56
  • 1
    $\begingroup$ 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? $\endgroup$
    – Neal Young
    Feb 8 '20 at 1:34
  • 2
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Feb 8 '20 at 1:40
2
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ Looks very related to 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. $\endgroup$ May 28 at 23:20
  • $\begingroup$ @RyanWilliams, interesting.. That does sound like a similar (probably stronger) result. $\endgroup$
    – Neal Young
    May 29 at 2:00
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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$? $\endgroup$ Feb 5 '20 at 5:52
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 5 '20 at 6:09
  • $\begingroup$ Also, do you happen to have a reference for: $\forall i, DTIME(n^{i}) \nsubseteq DTIME(n^{i-1})_{/o(n)}$ ? Thank you again! :) $\endgroup$ Feb 5 '20 at 6:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – PMercier
    Feb 5 '20 at 6:22
  • 2
    $\begingroup$ 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. $\endgroup$
    – PMercier
    Feb 5 '20 at 6:28

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.