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


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!

  • $\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$ – Michael Wehar 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$ – Michael Wehar 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$ – Michael Wehar 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

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.

  • $\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$ – Michael Wehar 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$ – Michael Wehar 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$ – Michael Wehar 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.