In Sipser, It is given Pg. 284

Let t(n) be a function, where t(n) ≥ n. Then every t(n) time non-deterministic single-tape Turing machine has an equivalent 2 O(t(n)) time deterministic single tape Turing machine

In the given proof, at end they conclude

O(t(n)bt(n)) = 2O(t(n)).

where b is the maximum number of legal choices given by N’stransition function

I am unable to understand how did they conclude so>

  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Apr 16 '17 at 19:11
  • $\begingroup$ Be aware of what "$2^{O(\dots)}$" means -- it's horrible abuse of notation. $\endgroup$ – Raphael Apr 16 '17 at 19:11

You can write, if $b\gt 1$, $$b^{t(n)}=2^{\log_2{b}\times t(n)}=2^{O(t(n))}$$

So, $$O(t(n)b^{t(n)})=O(t(n)2^{O(t(n))})=O(2^{\log_2{t(n)}}2^{O(t(n))})=2^{O(t(n))}$$

To elaborate, $$O(x2^{O(x)})=O(2^{\log x}2^{O(x)})=O(2^{O(x)+\log x})=O(2^{O(x)})$$ which means it is eventually upper bounded by some $$c2^{O(x)}=2^{\log cO(x)}=2^{O(x)}$$

Note that if $b=1$, then the non deterministic Turing machine is effectively a deterministic Turing machine, so you can still write it as $O(t(n))$, which is as expected.

  • $\begingroup$ You wrote, O(t(n) 2^x) = 2^x, in short in last step. But how does it prove that the deterministic turing machine can't take more than 2^x steps..?? $\endgroup$ – user2984602 Apr 16 '17 at 17:31
  • $\begingroup$ @user2984602 $O(x2^{O(x)})=O(2^{\log x}2^{O(x)})=O(2^{O(x)+\log x})=O(2^{O(x)})$, which means it is eventually upper bounded by some $c2^{O(x)}=2^{\log cO(x)}=2^{O(x)}$. Does this clarify your question? $\endgroup$ – GoodDeeds Apr 16 '17 at 18:36

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.