I am having some trouble understanding the equivalence of DTM's and NTM's. If you have Sipser its under 7.11; where he says that any NTM $N$ that halts after $t(n)$ steps has an equivalent DTM $D$ that halts after $2^{O(t(n))}$ steps.

He says that $N$ 's "computation tree" has at most $b^{t(n)}$ leaves, where $b$ is the maximum number of choices a transition can have in $N$, and the tree is at most $t(n)$ "levels deep", since $N$ halts after $t(n)$ steps per definition.

Now if one would like to simulate $N$ with $D$ you would have to go through no more than $t(n)b^{t(n)}$ steps to halt.

Then Sipser says that $O(t(n)b^{t(n)})= 2^{O(t(n))}$ which I dont understand.

In my understanding the runtime of $D$ should be $O(b^{t(n)})$ where $b >0$.

Can someone clear this up for me ?

Relevant pages in Sipser are 255-256.


The claim is that for constant $b$, if $f = O(t(n) b^{t(n)})$ then $f = 2^{O(t(n))}$. Indeed, $xb^x \leq b(b+1)^x$, and so $$ Ct(n) b^{t(n)} \leq Cb (1+b)^{t(n)} = 2^{\log_2(1+b) \cdot t(n) + \log_2 b + \log_2 C}. $$ From here it's not hard to check that $f = O(t(n)b^{t(n)})$ implies $f = 2^{O(t(n))}$.

  • $\begingroup$ i have some trouble understanding understanding your answer, can you elaborate on the middle formula (or point me to some resource where I can come to this conclusion myself ?) $\endgroup$ – zython Jun 18 '17 at 13:50
  • $\begingroup$ What is the "middle formula"? $\endgroup$ – Yuval Filmus Jun 18 '17 at 14:27
  • $\begingroup$ $Ct(n)$ ... until $2^{+\log_2 C}$, until then it is trivial, I dont understand how both sides are equal. $\endgroup$ – zython Jun 18 '17 at 14:30
  • $\begingroup$ I suggest reviewing logarithms and arithmetic of powers. $\endgroup$ – Yuval Filmus Jun 18 '17 at 14:32
  • $\begingroup$ sounds like a fair proposal. accepted $\endgroup$ – zython Jun 18 '17 at 14:37

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.