1
$\begingroup$

In the proof of the Time Hierarchy Theorem, Arora and Barak writes:

Consider the following Turing Machine $D$: “On input $x$, run for $|x|^{1.4}$ steps the Universal TM $U$ of Theorem 1.6 to simulate the execution of $M_x$ on $x$. If $M_x$ outputs an answer in this time, namely, $M_x(x)\in \{0,1\}$ then output the opposite answer (i.e., output $1−M_x(x)$). Else output $0$.” Here $M_x$ is the machine represented by the string $x$.

What if we give the encoding of $D$ as input to $D$? Then $D$ will accept exactly when $D$ will reject. So such a $D$ cannot even exist. Am I missing something?

$\endgroup$
1
  • $\begingroup$ Arora and Barak are two different people. $\endgroup$ Oct 6 '21 at 19:54
1
$\begingroup$

There will be no contradiction, since $D$ doesn't run in time $n^{1.4}$. In fact, what the proof of the time hierarchy theorem shows is that no equivalent Turing machine can run in time $n^{1.4}$, precisely because this will result in a contradiction. In other words, the language computed by $D$ lies outside of $\mathrm{DTIME}(n^{1.4})$. On the other hand, $D$ can be computed in time $O(n^{1.4} \log n)$. This shows that $$\mathrm{DTIME}(n^{1.4}) \subsetneq \mathrm{DTIME}(O(n^{1.4} \log n)).$$

(Usually $\mathrm{DTIME}(f(n))$ is defined as the class of problems which can be solved in time $O(f(n))$ rather than $f(n)$, the latter being the intended interpretation above. In that case the separation is between $\mathrm{DTIME}(f(n))$ and $\mathrm{DTIME}(n^{1.4} \log n)$ for any $f(n) = o(n^{1.4})$.)

$\endgroup$
8
  • $\begingroup$ In the proof in the book, this $D$ was defined to actually prove that $DTIME(n)\subset DTIME(n^2)$. So $D$ indeed lies in $DTIME(n^{1.4})$. Here is the link to the book: Page 84 in google.com/… $\endgroup$
    – Andrew22
    Oct 6 '21 at 19:50
  • $\begingroup$ Nevertheless, it can be used to prove a somewhat stronger separation. $\endgroup$ Oct 6 '21 at 19:51
  • $\begingroup$ Yes it can. But my question was what would happen when we give the string encoding of $D$ as input to $D$. $\endgroup$
    – Andrew22
    Oct 6 '21 at 19:58
  • $\begingroup$ It would output $0$, since $D$ takes more than $n^{1.4}$ time. $\endgroup$ Oct 6 '21 at 19:59
  • $\begingroup$ Could you please explain why it would take more than $n^{1.4}$ time? $\endgroup$
    – Andrew22
    Oct 6 '21 at 20:15

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.