3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

Your arguments is as follows:

  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.

$\endgroup$
  • $\begingroup$ Thanks! But with your correct running time for N, how would the contradiction of 1. and 4. be resolved? $\endgroup$ – John Smith Jul 18 '15 at 7:16
  • $\begingroup$ My earlier answer didn't make much sense. Hopefully the new one explains the difficulty. $\endgroup$ – Yuval Filmus Jul 18 '15 at 14:36
  • $\begingroup$ 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. $\endgroup$ – John Smith Jul 18 '15 at 14:58

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.