tag:blogger.com,1999:blog-3722233.post85410070..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Complexity Class of the Week: PPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-70503245759548213932022-02-15T14:38:01.402-06:002022-02-15T14:38:01.402-06:00Projected model counting is in PP^NP. I see that P...Projected model counting is in PP^NP. I see that PP^BQP = PP was known in 2002, is there anything known about PP^NP now?DMhttps://www.blogger.com/profile/09869079529680248008noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87962411938587482162020-03-29T10:14:28.777-05:002020-03-29T10:14:28.777-05:00You don't talk about the result of Scott Aaron...You don't talk about the result of Scott Aaronson:<br /><br />"Post-BQP = PP".<br /><br />And yet, some proofs of PP class in 'Quantum Computing'.<br /><br />My first comments here ... Awesome & amazing blog, bye !!!!skoxhttps://www.blogger.com/profile/05170994734879812229noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80227145903167140852014-11-18T13:31:33.969-06:002014-11-18T13:31:33.969-06:00That means that if you have an oracle for PP, you ...That means that if you have an oracle for PP, you can find the value of f(x), by doing binary search on k with L and therefore P^#P is in P^PP, correct? What about the other way (P^PP is in P^#P)? Even if you have an oracle for #P, how can you tell if more than half of the computational paths are accepting paths for an arbitrary problem? Antoniahttps://www.facebook.com/lovnis7noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49523568486801461542014-11-18T06:04:09.837-06:002014-11-18T06:04:09.837-06:00If f is a #P function then the language L={(x,k) |...If f is a #P function then the language L={(x,k) | f(x) >= k} is in PP. Then do binary search on k.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20517312119412268032014-11-17T22:27:05.960-06:002014-11-17T22:27:05.960-06:00How is it exactly that you prove P^PP = P^#P? You ...How is it exactly that you prove P^PP = P^#P? You said binary search, but I cant make sense of that.Antoniahttps://www.facebook.com/lovnis7noreply@blogger.com