# Question as regards a proof of the Time Hierarchy Theorem

I'm referring to the proof outlined here (and wikipedia.org): https://proofwiki.org/wiki/Deterministic_Time_Hierarchy_Theorem

In my understanding, if I relaxed the conditions such that $K$ decides the input in time $O(f(m)^3)$, there should not be a contradiction in the final step because an appropriate TM $K$ should really exist.

Under this condition, $N$'s running time should be $O(f(2n+1)^3)$.

Finally, I arrive at the conclusion:

1. If $N$ rejects $[N]$ (which we know it does in at most $f(2n+1)^3$ operations):
2. By the definition of $N$, $K$ accepts $([N],[N])$.
3. Therefore, by the definition of $K$, $([N],[N])\in H_f$.
4. Therefore, by the definition of $H_f$, $N$ does accept $[N]$ in $f(n)$ steps.

To me it seems that 1. and 4. would still contradict. What did I do wrong?

1. If $N$ rejects $[N]$ then $([N],[N]) \in H_f$.
2. Since $([N],[N]) \in H_f$, $N$ accepts $[N]$ in $f(m_n)$ steps.

This is indeed a contradiction, so we conclude that $N$ accepts $[N]$. Then we argue again:

1. Since $N$ accepts $[N]$ then $([N],[N]) \notin H_f$.
2. Since $([N],[N]) \notin H_f$, it is not true that $N$ accepts $[N]$ in $f(m_n)$ steps.

Since the running time of $N$ is $f(2m_n+1)^3$ in your case, there is no contradiction. After $f(m_n)$ steps the machine $N$ might still be running.

• Thanks! But with your correct running time for N, how would the contradiction of 1. and 4. be resolved? – John Smith Jul 18 '15 at 7:16
• My earlier answer didn't make much sense. Hopefully the new one explains the difficulty. – Yuval Filmus Jul 18 '15 at 14:36
• Ah yes, now I fully understand! I was actually aware that there is no contradiction when I chose the branch where N accepts but somehow I thought it was necessary to prove that both are free of contradictions. – John Smith Jul 18 '15 at 14:58