3
$\begingroup$

I saw two different definitions of time constructible functions.

In Sipser (third edt), Definition 9.8, defines $t(n)$ is time constructible if $t(n)\geq O(n \log n)$ and maps $1^n$ to the binary representation of $t(n)$ in time $O(t(n))$.

In arora, there is a lower bound $t(n) \geq n$ instead of $t(n) \geq O(n \log n)$ , so i wonder why there is factor $\log n$ in sipser definition ? What is wrong with $t(n) \geq n$ ? Is it because of single-tape multi-tape arguments ?

Is it because sipser version of time hierarchy theorem simulate a single tape TM by another single tape TM for a prespecified number of steps ?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ The version of the time hierarchy theorem in Anup Rao's notes states that $\mathsf{TIME}(r(n)) \neq \mathsf{TIME}(t(n))$ if $r,t$ are time constructible and $r\log r = o(t)$. He only requires $r(n),t(n) \geq n$, which implies that $t(n) = \omega(n\log n)$. Perhaps this is the source of the discrepancy — where the logarithmic factor comes from. $\endgroup$
    – Yuval Filmus
    Commented Aug 11, 2021 at 20:25
  • $\begingroup$ @YuvalFilmus Is it because computing $n$ in binary costs $n \log n$ ? As we know incrementing counter by one cost $\log n$ ? $\endgroup$
    – Omid Yaghoubi
    Commented Aug 12, 2021 at 14:29
  • $\begingroup$ There is logarithmic overhead in simulating a Turing machine. $\endgroup$
    – Yuval Filmus
    Commented Aug 12, 2021 at 14:35
  • $\begingroup$ @YuvalFilmus I know that, but if $t(n) \geq n$ so we compute $t(n)$ in binary and we count down for each step, in sipser version of THT , shifting counters bit is the cause of overhead. (But in arora , he use Efficient TM which introduced by Hennie and Stern) But my question is we only use time constructibility to compute $t(n)$ , why $t(n)$ must be greater than $n \log n$ instead of greater than $n$ ? $\endgroup$
    – Omid Yaghoubi
    Commented Aug 12, 2021 at 14:41
  • 2
    $\begingroup$ If $r(n) \ge n$ then $t(n) = \omega(n\log n)$. $\endgroup$
    – Yuval Filmus
    Commented Aug 12, 2021 at 14:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.