Is there a non-deterministic version of the complexity class PP?

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











up vote
2
down vote

favorite
1












From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?)






cc.complexity-theory complexity-classes time-complexity







share|cite|improve this question





















  • How would such a complexity class be defined?
    – Sasho Nikolov
    8 hours ago














up vote
2
down vote

favorite
1












From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?)






cc.complexity-theory complexity-classes time-complexity







share|cite|improve this question





















  • How would such a complexity class be defined?
    – Sasho Nikolov
    8 hours ago












up vote
2
down vote

favorite
1









up vote
2
down vote

favorite
1






1





From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?)






cc.complexity-theory complexity-classes time-complexity







share|cite|improve this question













From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?)






cc.complexity-theory complexity-classes time-complexity




cc.complexity-theory complexity-classes time-complexity






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 10 hours ago









user138901

334




334











  • How would such a complexity class be defined?
    – Sasho Nikolov
    8 hours ago
















  • How would such a complexity class be defined?
    – Sasho Nikolov
    8 hours ago















How would such a complexity class be defined?
– Sasho Nikolov
8 hours ago




How would such a complexity class be defined?
– Sasho Nikolov
8 hours ago










2 Answers
2






active

oldest

votes

















up vote
4
down vote













PP is defined as a probabilistic class and we don't normally think of nondeterministic versions of any of these classes (as far as I'm aware). In a sense probabilistic classes and nondeterministic ones are already on the same spectrum -- let me illustrate. We can define a language to be in PP if there's a randomized poly-time TM ("RPTM") that on a yes instance accepts with $> 0.5$ probability and on a no instance accepts with $leq 0.5$ probability. Similarly we can define a language to be in NP if there's a RPTM accepting yes-instances w.prob $> 0$ and accepting no-instances w.prob $0$. (Convince yourself of this if you haven't before.) BPP corresponds to probability thresholds $geq 2/3$ and $leq 1/3$ while RP corresponds to $geq 1/2$ and $0$.



So you see, PP can already be viewed as a "nondeterministic" version of P, but with different requirements as compared to NP.






share|cite|improve this answer



























    up vote
    2
    down vote













    It does not really make sense to define an “X-version of class Y”, this is a misguided viewpoint. You define classes because they are useful or interesting in whatever context you are investigating, not to fill a slot in an imaginary table. So, what would count as a nondeterministic version of PP depends very much on what you intend to do with the class.



    Having said that, in view of $mathrmP^=PP$, one reasonable option is to define a nondeterministic version of PP as $mathrmNP^$. Actually, this should equal $existsmathrmPP$.






    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: "114"
      ;
      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: "",
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      );



      );













       

      draft saved


      draft discarded


















      StackExchange.ready(
      function ()
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f41726%2fis-there-a-non-deterministic-version-of-the-complexity-class-pp%23new-answer', 'question_page');

      );

      Post as a guest

















      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      4
      down vote













      PP is defined as a probabilistic class and we don't normally think of nondeterministic versions of any of these classes (as far as I'm aware). In a sense probabilistic classes and nondeterministic ones are already on the same spectrum -- let me illustrate. We can define a language to be in PP if there's a randomized poly-time TM ("RPTM") that on a yes instance accepts with $> 0.5$ probability and on a no instance accepts with $leq 0.5$ probability. Similarly we can define a language to be in NP if there's a RPTM accepting yes-instances w.prob $> 0$ and accepting no-instances w.prob $0$. (Convince yourself of this if you haven't before.) BPP corresponds to probability thresholds $geq 2/3$ and $leq 1/3$ while RP corresponds to $geq 1/2$ and $0$.



      So you see, PP can already be viewed as a "nondeterministic" version of P, but with different requirements as compared to NP.






      share|cite|improve this answer
























        up vote
        4
        down vote













        PP is defined as a probabilistic class and we don't normally think of nondeterministic versions of any of these classes (as far as I'm aware). In a sense probabilistic classes and nondeterministic ones are already on the same spectrum -- let me illustrate. We can define a language to be in PP if there's a randomized poly-time TM ("RPTM") that on a yes instance accepts with $> 0.5$ probability and on a no instance accepts with $leq 0.5$ probability. Similarly we can define a language to be in NP if there's a RPTM accepting yes-instances w.prob $> 0$ and accepting no-instances w.prob $0$. (Convince yourself of this if you haven't before.) BPP corresponds to probability thresholds $geq 2/3$ and $leq 1/3$ while RP corresponds to $geq 1/2$ and $0$.



        So you see, PP can already be viewed as a "nondeterministic" version of P, but with different requirements as compared to NP.






        share|cite|improve this answer






















          up vote
          4
          down vote










          up vote
          4
          down vote









          PP is defined as a probabilistic class and we don't normally think of nondeterministic versions of any of these classes (as far as I'm aware). In a sense probabilistic classes and nondeterministic ones are already on the same spectrum -- let me illustrate. We can define a language to be in PP if there's a randomized poly-time TM ("RPTM") that on a yes instance accepts with $> 0.5$ probability and on a no instance accepts with $leq 0.5$ probability. Similarly we can define a language to be in NP if there's a RPTM accepting yes-instances w.prob $> 0$ and accepting no-instances w.prob $0$. (Convince yourself of this if you haven't before.) BPP corresponds to probability thresholds $geq 2/3$ and $leq 1/3$ while RP corresponds to $geq 1/2$ and $0$.



          So you see, PP can already be viewed as a "nondeterministic" version of P, but with different requirements as compared to NP.






          share|cite|improve this answer












          PP is defined as a probabilistic class and we don't normally think of nondeterministic versions of any of these classes (as far as I'm aware). In a sense probabilistic classes and nondeterministic ones are already on the same spectrum -- let me illustrate. We can define a language to be in PP if there's a randomized poly-time TM ("RPTM") that on a yes instance accepts with $> 0.5$ probability and on a no instance accepts with $leq 0.5$ probability. Similarly we can define a language to be in NP if there's a RPTM accepting yes-instances w.prob $> 0$ and accepting no-instances w.prob $0$. (Convince yourself of this if you haven't before.) BPP corresponds to probability thresholds $geq 2/3$ and $leq 1/3$ while RP corresponds to $geq 1/2$ and $0$.



          So you see, PP can already be viewed as a "nondeterministic" version of P, but with different requirements as compared to NP.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 4 hours ago









          usul

          5,01911435




          5,01911435




















              up vote
              2
              down vote













              It does not really make sense to define an “X-version of class Y”, this is a misguided viewpoint. You define classes because they are useful or interesting in whatever context you are investigating, not to fill a slot in an imaginary table. So, what would count as a nondeterministic version of PP depends very much on what you intend to do with the class.



              Having said that, in view of $mathrmP^=PP$, one reasonable option is to define a nondeterministic version of PP as $mathrmNP^$. Actually, this should equal $existsmathrmPP$.






              share|cite|improve this answer
























                up vote
                2
                down vote













                It does not really make sense to define an “X-version of class Y”, this is a misguided viewpoint. You define classes because they are useful or interesting in whatever context you are investigating, not to fill a slot in an imaginary table. So, what would count as a nondeterministic version of PP depends very much on what you intend to do with the class.



                Having said that, in view of $mathrmP^=PP$, one reasonable option is to define a nondeterministic version of PP as $mathrmNP^$. Actually, this should equal $existsmathrmPP$.






                share|cite|improve this answer






















                  up vote
                  2
                  down vote










                  up vote
                  2
                  down vote









                  It does not really make sense to define an “X-version of class Y”, this is a misguided viewpoint. You define classes because they are useful or interesting in whatever context you are investigating, not to fill a slot in an imaginary table. So, what would count as a nondeterministic version of PP depends very much on what you intend to do with the class.



                  Having said that, in view of $mathrmP^=PP$, one reasonable option is to define a nondeterministic version of PP as $mathrmNP^$. Actually, this should equal $existsmathrmPP$.






                  share|cite|improve this answer












                  It does not really make sense to define an “X-version of class Y”, this is a misguided viewpoint. You define classes because they are useful or interesting in whatever context you are investigating, not to fill a slot in an imaginary table. So, what would count as a nondeterministic version of PP depends very much on what you intend to do with the class.



                  Having said that, in view of $mathrmP^=PP$, one reasonable option is to define a nondeterministic version of PP as $mathrmNP^$. Actually, this should equal $existsmathrmPP$.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered 2 hours ago









                  Emil Jeřábek

                  10.3k33459




                  10.3k33459



























                       

                      draft saved


                      draft discarded















































                       


                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function ()
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcstheory.stackexchange.com%2fquestions%2f41726%2fis-there-a-non-deterministic-version-of-the-complexity-class-pp%23new-answer', 'question_page');

                      );

                      Post as a guest
































































                      Comments

                      Post a Comment

                      Popular posts from this blog

                      What does second last employer means? [closed]

                      Image
                      Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote -3 down vote favorite Say, for example I have worked in the following companies, Company A => 2010 - 2011 Company B => 2011 - 2012 Company C => 2012 - Till Date Company D => Have offer Now assume Company D is asking to submit documents from my second last employer. So from the list of companies given, which company would be qualified as second last employer? software-industry employer share | improve this question asked Aug 10 '14 at 5:16 Rajaprabhu Aravindasamy 559 1 6 13 closed as off-topic by Jim G., jmort253 ♦ Aug 11 '14 at 1:58 This question appears to be off-topic. The users who voted to close gave this specific reason: "Questions seeking advice on company-specific regulations, agreements, or policies should be directed to your manager or HR department. Questions that address...
                      Read more

                      List of Gilmore Girls characters

                      Image
                      The season three cast—(Back row): Lane, Michel, Paris, Emily, Richard, Sookie, Miss Patty, Kirk; Front row: Jess, Luke, Lorelai, Rory, Dean This is a list of characters for the comedy-drama television series Gilmore Girls . Contents 1 Main characters 1.1 Lorelai Gilmore 1.2 Rory Gilmore 1.3 Sookie St. James 1.4 Lane Kim 1.5 Michel Gerard 1.6 Luke Danes 1.7 Emily Gilmore 1.8 Richard Gilmore 1.9 Paris Geller 1.10 Dean Forester 1.11 Jess Mariano 1.12 Kirk Gleason 1.13 Jason Stiles 1.14 Logan Huntzberger 2 Major recurring characters 2.1 Christopher Hayden 2.2 Jackson Belleville 2.3 Mrs. Kim 2.4 Tristin DuGray 2.5 Max Medina 2.6 Taylor Doose 2.7 Dave Rygalski 2.8 Marty 3 Recurring characters 3.1 Stars Hollow 3.2 Chilton 3.3 Yale 3.4 Other 4 Notable guest stars 5 Unseen characters 6 Notes 7 References Main characters Actor Character Appearances Season 1 Season 2 Season 3 Season 4 Season 5 Season 6 Season 7 A Year in the Life Lauren Graham Lorelai Gilmore...
                      Read more

                      Confectionery

                      Image
                      Prepared foods made with a lot of sugar or other cabohydrates "Sweetmeat" redirects here. For the racehorse, see Sweetmeat (horse). Not to be confused with Sweetbread. This Kransekake is a traditional Scandinavian baker's confection. Confectionery is the art of making confections , which are food items that are rich in sugar and carbohydrates. Exact definitions are difficult. [1] In general, though, confectionery is divided into two broad and somewhat overlapping categories, bakers' confections and sugar confections. [2] Bakers' confectionery, also called flour confections , includes principally sweet pastries, cakes, and similar baked goods. Sugar confectionery includes candies ( sweets in British English), candied nuts, chocolates, chewing gum, bubble gum, pastillage, and other confections that are made primarily of sugar. In some cases, chocolate confections (confections made of chocolate) are treated as a separate category, as are sugar-free versions of ...
                      Read more