2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\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, 2017 at 13:50
  • $\begingroup$ What is the "middle formula"? $\endgroup$
    – Yuval Filmus
    Jun 18, 2017 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, 2017 at 14:30
  • $\begingroup$ I suggest reviewing logarithms and arithmetic of powers. $\endgroup$
    – Yuval Filmus
    Jun 18, 2017 at 14:32
  • $\begingroup$ sounds like a fair proposal. accepted $\endgroup$
    – zython
    Jun 18, 2017 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.