If a non-deterministic Turing machine runs in f(n) space, then why does it run in 2^O(f(n)) time?

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP












1












$begingroup$


Assuming that f(n) >= n.



If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, but in Turing machines a tape cell could hold any number of symbols. I'm having trouble why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape.










share|cite|improve this question









$endgroup$











  • $begingroup$
    That is the worst case. As is also shown by the use of O notation. It is commonly referred to the encoding in the CLRS. Since every character can be encoded in a minimum of 2 characters. If you encode using only one than you will have a linear complexity in input length rather than the logarithmic complexity the binary encoding offers. Which when applied to a linear problem will give a theoretical exponential complexity. Please refer to CLRS, Introduction to Algorithms part on NP completeness for better explanation.
    $endgroup$
    – anon
    Jan 1 at 23:16















1












$begingroup$


Assuming that f(n) >= n.



If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, but in Turing machines a tape cell could hold any number of symbols. I'm having trouble why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape.










share|cite|improve this question









$endgroup$











  • $begingroup$
    That is the worst case. As is also shown by the use of O notation. It is commonly referred to the encoding in the CLRS. Since every character can be encoded in a minimum of 2 characters. If you encode using only one than you will have a linear complexity in input length rather than the logarithmic complexity the binary encoding offers. Which when applied to a linear problem will give a theoretical exponential complexity. Please refer to CLRS, Introduction to Algorithms part on NP completeness for better explanation.
    $endgroup$
    – anon
    Jan 1 at 23:16













1












1








1





$begingroup$


Assuming that f(n) >= n.



If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, but in Turing machines a tape cell could hold any number of symbols. I'm having trouble why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape.










share|cite|improve this question









$endgroup$




Assuming that f(n) >= n.



If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, but in Turing machines a tape cell could hold any number of symbols. I'm having trouble why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape.







complexity-theory turing-machines






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Jan 1 at 22:02









Taking1n1Taking1n1

62




62











  • $begingroup$
    That is the worst case. As is also shown by the use of O notation. It is commonly referred to the encoding in the CLRS. Since every character can be encoded in a minimum of 2 characters. If you encode using only one than you will have a linear complexity in input length rather than the logarithmic complexity the binary encoding offers. Which when applied to a linear problem will give a theoretical exponential complexity. Please refer to CLRS, Introduction to Algorithms part on NP completeness for better explanation.
    $endgroup$
    – anon
    Jan 1 at 23:16
















  • $begingroup$
    That is the worst case. As is also shown by the use of O notation. It is commonly referred to the encoding in the CLRS. Since every character can be encoded in a minimum of 2 characters. If you encode using only one than you will have a linear complexity in input length rather than the logarithmic complexity the binary encoding offers. Which when applied to a linear problem will give a theoretical exponential complexity. Please refer to CLRS, Introduction to Algorithms part on NP completeness for better explanation.
    $endgroup$
    – anon
    Jan 1 at 23:16















$begingroup$
That is the worst case. As is also shown by the use of O notation. It is commonly referred to the encoding in the CLRS. Since every character can be encoded in a minimum of 2 characters. If you encode using only one than you will have a linear complexity in input length rather than the logarithmic complexity the binary encoding offers. Which when applied to a linear problem will give a theoretical exponential complexity. Please refer to CLRS, Introduction to Algorithms part on NP completeness for better explanation.
$endgroup$
– anon
Jan 1 at 23:16




$begingroup$
That is the worst case. As is also shown by the use of O notation. It is commonly referred to the encoding in the CLRS. Since every character can be encoded in a minimum of 2 characters. If you encode using only one than you will have a linear complexity in input length rather than the logarithmic complexity the binary encoding offers. Which when applied to a linear problem will give a theoretical exponential complexity. Please refer to CLRS, Introduction to Algorithms part on NP completeness for better explanation.
$endgroup$
– anon
Jan 1 at 23:16










2 Answers
2






active

oldest

votes


















3












$begingroup$


why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape?




Because it does not matter in the sense that $2^O(f(n)) = b^O(f(n))$ for any positive $b > 1$.



Using the popular set-theoretic understanding of the big $O$-notation, we have
$$beginalign
2^O(f(n))&=2^g(n)mid g(n)in O(f(n)) \
&=left(b^log_b2right)^g(n)mid g(n)in O(f(n)) \
&=b^h(n)mid exists g(n), h(n)= (log_b2)g(n), g(n)in O(f(n)) \
&=b^h(n)mid h(n)in O(f(n)) \
&=b^O(f(n))endalign$$



By the way, there is no need to assume $f(n)ge n$. For example, all above hold when $f(n) = lceilsqrt nrceil$ or $f(n) = lceillog_2nrceil$.






share|cite|improve this answer











$endgroup$




















    0












    $begingroup$

    Because an exponential function to any base can be expressed in terms of any exponential function of another base, in a way which also happens to make this possible. Namely, for any real number $a > 0$, $a^x = 2^lg(a) x$. Thus if you have $a^O(f(n))$ it is the same as $2^lg(a) O(f(n))$. But a constant multiplying a big-O simply gets absorbed into it, since the whole point of the notation is that it's the shape, not the scale, of the function wrapped by it that counts.






    share|cite|improve this answer









    $endgroup$












      Your Answer





      StackExchange.ifUsing("editor", function ()
      return StackExchange.using("mathjaxEditing", function ()
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      );
      );
      , "mathjax-editing");

      StackExchange.ready(function()
      var channelOptions =
      tags: "".split(" "),
      id: "419"
      ;
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function()
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled)
      StackExchange.using("snippets", function()
      createEditor();
      );

      else
      createEditor();

      );

      function createEditor()
      StackExchange.prepareEditor(
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: false,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: null,
      bindNavPrevention: true,
      postfix: "",
      imageUploader:
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      ,
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      );



      );













      draft saved

      draft discarded


















      StackExchange.ready(
      function ()
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102260%2fif-a-non-deterministic-turing-machine-runs-in-fn-space-then-why-does-it-run-i%23new-answer', 'question_page');

      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      3












      $begingroup$


      why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape?




      Because it does not matter in the sense that $2^O(f(n)) = b^O(f(n))$ for any positive $b > 1$.



      Using the popular set-theoretic understanding of the big $O$-notation, we have
      $$beginalign
      2^O(f(n))&=2^g(n)mid g(n)in O(f(n)) \
      &=left(b^log_b2right)^g(n)mid g(n)in O(f(n)) \
      &=b^h(n)mid exists g(n), h(n)= (log_b2)g(n), g(n)in O(f(n)) \
      &=b^h(n)mid h(n)in O(f(n)) \
      &=b^O(f(n))endalign$$



      By the way, there is no need to assume $f(n)ge n$. For example, all above hold when $f(n) = lceilsqrt nrceil$ or $f(n) = lceillog_2nrceil$.






      share|cite|improve this answer











      $endgroup$

















        3












        $begingroup$


        why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape?




        Because it does not matter in the sense that $2^O(f(n)) = b^O(f(n))$ for any positive $b > 1$.



        Using the popular set-theoretic understanding of the big $O$-notation, we have
        $$beginalign
        2^O(f(n))&=2^g(n)mid g(n)in O(f(n)) \
        &=left(b^log_b2right)^g(n)mid g(n)in O(f(n)) \
        &=b^h(n)mid exists g(n), h(n)= (log_b2)g(n), g(n)in O(f(n)) \
        &=b^h(n)mid h(n)in O(f(n)) \
        &=b^O(f(n))endalign$$



        By the way, there is no need to assume $f(n)ge n$. For example, all above hold when $f(n) = lceilsqrt nrceil$ or $f(n) = lceillog_2nrceil$.






        share|cite|improve this answer











        $endgroup$















          3












          3








          3





          $begingroup$


          why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape?




          Because it does not matter in the sense that $2^O(f(n)) = b^O(f(n))$ for any positive $b > 1$.



          Using the popular set-theoretic understanding of the big $O$-notation, we have
          $$beginalign
          2^O(f(n))&=2^g(n)mid g(n)in O(f(n)) \
          &=left(b^log_b2right)^g(n)mid g(n)in O(f(n)) \
          &=b^h(n)mid exists g(n), h(n)= (log_b2)g(n), g(n)in O(f(n)) \
          &=b^h(n)mid h(n)in O(f(n)) \
          &=b^O(f(n))endalign$$



          By the way, there is no need to assume $f(n)ge n$. For example, all above hold when $f(n) = lceilsqrt nrceil$ or $f(n) = lceillog_2nrceil$.






          share|cite|improve this answer











          $endgroup$




          why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape?




          Because it does not matter in the sense that $2^O(f(n)) = b^O(f(n))$ for any positive $b > 1$.



          Using the popular set-theoretic understanding of the big $O$-notation, we have
          $$beginalign
          2^O(f(n))&=2^g(n)mid g(n)in O(f(n)) \
          &=left(b^log_b2right)^g(n)mid g(n)in O(f(n)) \
          &=b^h(n)mid exists g(n), h(n)= (log_b2)g(n), g(n)in O(f(n)) \
          &=b^h(n)mid h(n)in O(f(n)) \
          &=b^O(f(n))endalign$$



          By the way, there is no need to assume $f(n)ge n$. For example, all above hold when $f(n) = lceilsqrt nrceil$ or $f(n) = lceillog_2nrceil$.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Jan 2 at 5:49

























          answered Jan 2 at 0:19









          Apass.JackApass.Jack

          8,1521633




          8,1521633





















              0












              $begingroup$

              Because an exponential function to any base can be expressed in terms of any exponential function of another base, in a way which also happens to make this possible. Namely, for any real number $a > 0$, $a^x = 2^lg(a) x$. Thus if you have $a^O(f(n))$ it is the same as $2^lg(a) O(f(n))$. But a constant multiplying a big-O simply gets absorbed into it, since the whole point of the notation is that it's the shape, not the scale, of the function wrapped by it that counts.






              share|cite|improve this answer









              $endgroup$

















                0












                $begingroup$

                Because an exponential function to any base can be expressed in terms of any exponential function of another base, in a way which also happens to make this possible. Namely, for any real number $a > 0$, $a^x = 2^lg(a) x$. Thus if you have $a^O(f(n))$ it is the same as $2^lg(a) O(f(n))$. But a constant multiplying a big-O simply gets absorbed into it, since the whole point of the notation is that it's the shape, not the scale, of the function wrapped by it that counts.






                share|cite|improve this answer









                $endgroup$















                  0












                  0








                  0





                  $begingroup$

                  Because an exponential function to any base can be expressed in terms of any exponential function of another base, in a way which also happens to make this possible. Namely, for any real number $a > 0$, $a^x = 2^lg(a) x$. Thus if you have $a^O(f(n))$ it is the same as $2^lg(a) O(f(n))$. But a constant multiplying a big-O simply gets absorbed into it, since the whole point of the notation is that it's the shape, not the scale, of the function wrapped by it that counts.






                  share|cite|improve this answer









                  $endgroup$



                  Because an exponential function to any base can be expressed in terms of any exponential function of another base, in a way which also happens to make this possible. Namely, for any real number $a > 0$, $a^x = 2^lg(a) x$. Thus if you have $a^O(f(n))$ it is the same as $2^lg(a) O(f(n))$. But a constant multiplying a big-O simply gets absorbed into it, since the whole point of the notation is that it's the shape, not the scale, of the function wrapped by it that counts.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Jan 2 at 5:14









                  The_SympathizerThe_Sympathizer

                  1011




                  1011



























                      draft saved

                      draft discarded
















































                      Thanks for contributing an answer to Computer Science Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid


                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.

                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function ()
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102260%2fif-a-non-deterministic-turing-machine-runs-in-fn-space-then-why-does-it-run-i%23new-answer', 'question_page');

                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown






                      Popular posts from this blog

                      How to check contact read email or not when send email to Individual?

                      Displaying single band from multi-band raster using QGIS

                      How many registers does an x86_64 CPU actually have?