tag:blogger.com,1999:blog-3722233.post85410070..comments2024-10-03T16:28:40.297-05:00Comments on Computational Complexity: Complexity Class of the Week: PPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-4216917112263625192024-09-16T01:15:36.129-05:002024-09-16T01:15:36.129-05:00Is there a theorem L^PL=L^#L? The same idea of bin...Is there a theorem L^PL=L^#L? The same idea of binary search. Does it work? If not why not? What is the consequence if we have such a theorem?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55558228707490379112024-05-09T09:15:00.712-05:002024-05-09T09:15:00.712-05:00You can use the #P oracle to separately count the ...You can use the #P oracle to separately count the number of accepting and rejecting paths and see which is larger.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag: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