most recent 30 from http://mathoverflow.net 2013-05-25T13:23:56Z http://mathoverflow.net/feeds/question/10726 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10726/bpp-being-equal-to-p-under-oracle Sid 2010-01-04T18:17:29Z 2010-01-05T03:14:15Z

<p>Luca Trevisan <a href="http://lucatrevisan.wordpress.com/2008/02/16/approximate-counting/" rel="nofollow">here</a> gives a randomized polynomial-time approximation algorithm for #3-coloring given an NP oracle.</p> <p>In a similar vein, I was wondering if there were any results on $BPP^{NP}\stackrel{?}{=}$ #P - i.e. outputting a correct count for a #P problem under the presence of an NP oracle with high probability. The ideal result of course would tell whether they were equal or not but since we don't know whether P=#P or P=BPP, we can't prove the above false. So I'm also interested in any results that provide evidence either way or prove the above is true (which I'm guessing it is unlikely to be).</p> <p>If there are no such results, then is $BPP^{NP}$ generally believed to be equal to #P? </p> <p>**Edit: ** As per Mariano's suggestion, <a href="http://qwiki.stanford.edu/wiki/Complexity%5FZoo%3AB#bpp" rel="nofollow">Here</a>'s the Complexity Zoo's excellent description of the complexity class BPP. And <a href="http://qwiki.stanford.edu/wiki/Complexity%5FZoo%3ASymbols#sharpp" rel="nofollow">here</a> is the description of the complexity class #P.</p> <p>Thanks</p>

http://mathoverflow.net/questions/10726/bpp-being-equal-to-p-under-oracle/10774#10774 Rune 2010-01-05T03:14:15Z 2010-01-05T03:14:15Z

<p>First, let's be slightly pedantic and not make statements like P = #P, which cannot possibly be true just because P is a set of decision problems and #P is not. To get a decision version of #P, one can use PP, or something like P^#P.</p> <p>About your question, BPP^NP is contained in P^PP and P^#P by Toda's theorem. On the other hand, if P^#P were contained in BPP^NP, it would imply that PH is contained in BPP^NP, which would collapse the polynomial hierarchy to the third (or second?) level, which is considered unlikely. </p> <p>In conclusion, P^#P is considered to be more powerful than NP, BPP, BPP^NP and even NP^{NP^NP}.</p>