Is exponentiation in P?

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











up vote
3
down vote

favorite












I think the following problem belong to class P, but I don't know how I can prove it, could somebody help me?



  • Inputs: two numbers $(a,b) in mathbbN$

  • Output: $a^b$









share|cite|improve this question























  • I don't really see the connection between your two questions, so I have removed the second one.
    – Yuval Filmus
    4 hours ago















up vote
3
down vote

favorite












I think the following problem belong to class P, but I don't know how I can prove it, could somebody help me?



  • Inputs: two numbers $(a,b) in mathbbN$

  • Output: $a^b$









share|cite|improve this question























  • I don't really see the connection between your two questions, so I have removed the second one.
    – Yuval Filmus
    4 hours ago













up vote
3
down vote

favorite









up vote
3
down vote

favorite











I think the following problem belong to class P, but I don't know how I can prove it, could somebody help me?



  • Inputs: two numbers $(a,b) in mathbbN$

  • Output: $a^b$









share|cite|improve this question















I think the following problem belong to class P, but I don't know how I can prove it, could somebody help me?



  • Inputs: two numbers $(a,b) in mathbbN$

  • Output: $a^b$






complexity-theory complexity-classes






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 4 hours ago









Yuval Filmus

184k12175335




184k12175335










asked 5 hours ago









linkho

213




213











  • I don't really see the connection between your two questions, so I have removed the second one.
    – Yuval Filmus
    4 hours ago

















  • I don't really see the connection between your two questions, so I have removed the second one.
    – Yuval Filmus
    4 hours ago
















I don't really see the connection between your two questions, so I have removed the second one.
– Yuval Filmus
4 hours ago





I don't really see the connection between your two questions, so I have removed the second one.
– Yuval Filmus
4 hours ago











1 Answer
1






active

oldest

votes

















up vote
3
down vote













Your problem is not in P, for two different reasons:



  1. P is a class of decision problems, but your problem is a function problem. Instead of P, you should consider its functional equivalent FP.


  2. The output could be exponentially large in the input length: encoding $b$ takes about $log b$ bits, but encoding $a^b$ takes about $b log a$ bits.


This still leaves open the possibility that the following problem is in P:




Given natural numbers $a,b$ and an index $i$, determine the $i$th bit of $a^b$.




While I don't know what the answer to this question is, here is a related problem in FP:




Given natural numbers $a,b,c$, determine $a^b bmod c$.




This can be shown using the important technique of repeated squaring.






share|cite|improve this answer




















    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',
    convertImagesToLinks: false,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    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%2f98881%2fis-exponentiation-in-p%23new-answer', 'question_page');

    );

    Post as a guest






























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    3
    down vote













    Your problem is not in P, for two different reasons:



    1. P is a class of decision problems, but your problem is a function problem. Instead of P, you should consider its functional equivalent FP.


    2. The output could be exponentially large in the input length: encoding $b$ takes about $log b$ bits, but encoding $a^b$ takes about $b log a$ bits.


    This still leaves open the possibility that the following problem is in P:




    Given natural numbers $a,b$ and an index $i$, determine the $i$th bit of $a^b$.




    While I don't know what the answer to this question is, here is a related problem in FP:




    Given natural numbers $a,b,c$, determine $a^b bmod c$.




    This can be shown using the important technique of repeated squaring.






    share|cite|improve this answer
























      up vote
      3
      down vote













      Your problem is not in P, for two different reasons:



      1. P is a class of decision problems, but your problem is a function problem. Instead of P, you should consider its functional equivalent FP.


      2. The output could be exponentially large in the input length: encoding $b$ takes about $log b$ bits, but encoding $a^b$ takes about $b log a$ bits.


      This still leaves open the possibility that the following problem is in P:




      Given natural numbers $a,b$ and an index $i$, determine the $i$th bit of $a^b$.




      While I don't know what the answer to this question is, here is a related problem in FP:




      Given natural numbers $a,b,c$, determine $a^b bmod c$.




      This can be shown using the important technique of repeated squaring.






      share|cite|improve this answer






















        up vote
        3
        down vote










        up vote
        3
        down vote









        Your problem is not in P, for two different reasons:



        1. P is a class of decision problems, but your problem is a function problem. Instead of P, you should consider its functional equivalent FP.


        2. The output could be exponentially large in the input length: encoding $b$ takes about $log b$ bits, but encoding $a^b$ takes about $b log a$ bits.


        This still leaves open the possibility that the following problem is in P:




        Given natural numbers $a,b$ and an index $i$, determine the $i$th bit of $a^b$.




        While I don't know what the answer to this question is, here is a related problem in FP:




        Given natural numbers $a,b,c$, determine $a^b bmod c$.




        This can be shown using the important technique of repeated squaring.






        share|cite|improve this answer












        Your problem is not in P, for two different reasons:



        1. P is a class of decision problems, but your problem is a function problem. Instead of P, you should consider its functional equivalent FP.


        2. The output could be exponentially large in the input length: encoding $b$ takes about $log b$ bits, but encoding $a^b$ takes about $b log a$ bits.


        This still leaves open the possibility that the following problem is in P:




        Given natural numbers $a,b$ and an index $i$, determine the $i$th bit of $a^b$.




        While I don't know what the answer to this question is, here is a related problem in FP:




        Given natural numbers $a,b,c$, determine $a^b bmod c$.




        This can be shown using the important technique of repeated squaring.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 3 hours ago









        Yuval Filmus

        184k12175335




        184k12175335



























             

            draft saved


            draft discarded















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f98881%2fis-exponentiation-in-p%23new-answer', 'question_page');

            );

            Post as a guest













































































            Comments

            Popular posts from this blog

            What does second last employer means? [closed]

            Installing NextGIS Connect into QGIS 3?

            One-line joke