# single tape NTM to single tape DTM equivalence

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.

## 1 Answer

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))}$.

• 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 ?) Jun 18, 2017 at 13:50
• What is the "middle formula"? Jun 18, 2017 at 14:27
• $Ct(n)$ ... until $2^{+\log_2 C}$, until then it is trivial, I dont understand how both sides are equal. Jun 18, 2017 at 14:30
• I suggest reviewing logarithms and arithmetic of powers. Jun 18, 2017 at 14:32
• sounds like a fair proposal. accepted Jun 18, 2017 at 14:37