2
$\begingroup$

I would like something like this to be true:

Conjecture: There is a function $g(n)$ such that for all functions $f(n)$ (perhaps satisfying some reasonable properties, like time-constructability), there is a language in $TIME[f(n)]$ that is not in $TIME[f(n) - g(n)]$.

Is anything like this known? Can this be proven under any reasonable assumptions? Would this have any interesting consequences?

By $TIME[f(n)]$, I mean the set of problems solved by a Turing machine that halts in exactly $f(n)$ steps or less - not to be confused with $O(f(n))$ or less, in which case the conjecture is trivially false when $f(n) >> g(n)$.

$\endgroup$
  • $\begingroup$ Separations are by diagonalization and require simulation of the smaller class, and simulation requires asymptotically dominating the smaller function. Furthermore, I think what you want would contradict speed up theorems. $\endgroup$ – Kaveh Jun 9 '14 at 3:25
3
$\begingroup$

I don't see the need for your clarification, since through linear speed-up those sets are exactly the same. It is clear why you need to avoid using asymptotics, since $f(n)-g(n)$ and $f(n)$ are asymptotically the same, but not using asymptotics doesn't somehow make the linear speed-up theorem not true.

Some further insight can be gained. $g(n)$ is actually $g(f(n))$,i.e. it must depend on $f(n)$ to work for all functions. Why? Suppose g(n) is non-constant. Pick $f(n) = 2 g(n)$ . Then clearly $f(n)$ and $f(n)-g(n)$ are equal by the linear speed-up theorem. If $g(n)=c$ is constant, then we can pick a non-constant $f(n)$ so that the conjecture doesn't hold.

What if we allow dependency on $f(n)$? Well then by taking the known deterministic hierarchy theorem and doing some basic arithmetic we can see that any $g(f(n))$ that is $o((1 - \frac{1}{ \log f(n)} ) f(n) )$ works. However I am not sure if just by stating the same theorem in a slightly different form opens up the possibility of some new insight.

$\endgroup$
  • $\begingroup$ How does this contradict the speedup theorem? The speedup theorem doesn't say all functions can be sped up, just that there exist some that can't. Why can't there be one function that can't be sped up and another that can? $\endgroup$ – Geoffrey Irving Jun 9 '14 at 19:02
  • 1
    $\begingroup$ The speedup theorem is something I should have seen coming, but it doesn't exactly answer the spirit of the question. Perhaps I should have said that the TMs must have alphabet $\{0, 1, B\}$ to disallow this sort of trick. $\endgroup$ – GMB Jun 9 '14 at 21:06

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.