5
$\begingroup$

The time hierarchy theorem states that

$DTIME(f(n)) \neq DTIME(f(n)\log(f(n)))$

(Let me acknowledge that this statement isn't 100 percent accurate because f must be "time constructible" and potentially other things that I'm missing)

If we were to take some function f, we can consider

$DTIME(f(n)) \subset DTIME(f(n)\sqrt{\log(f(n))})\subset DTIME(f(n)\log(f(n)))$

Where we know that at least one of these inclusions is strict. Do we know of examples where one of these inclusions isn't?

In general we might want to prove that $DTIME(f(n)) \neq DTIME(f(n)g(f(n)))$ for a function $g$ which is as small as possible. Do we have better upper bounds on $g$ (like $g(n) = \log\log n$)? do we have non-trivial lower bounds on $g$ in the form of some (time constructible) $f$ for which $DTIME(f(n) = DTIME(f(n)g(f(n)))$?

$\endgroup$
  • 3
    $\begingroup$ The time hierarchy theorem as stated is the strongest time hierarchy theorem currently known. However, there is no reason to suspect that a stronger statement is not true. $\endgroup$ – Yuval Filmus Jan 6 '17 at 18:57
1
$\begingroup$

IMHO, there cannot be better, stricter Time Hierarchy Theorem everywhere.

To improve this theorem, you need faster Universal Turing Machine. The $log(n)$ overhead of the currently fastest simulation technique seems to be unavoidable, especially for large enough time bounds, since with more time resource the simulated TM can do crazy things that the UTM cannot assume some regular property to do the simulation faster.

With small time bounds, there may be some improvements. But, its consequences are negligible.

$\endgroup$

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.