BPP being equal to #P under Oracle - MathOverflow 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 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 Answer by Rune for BPP being equal to #P under Oracle 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<sup>#P</sup>.</p> <p>About your question, BPP<sup>NP</sup> is contained in P<sup>PP</sup> and P<sup>#P</sup> by Toda's theorem. On the other hand, if P<sup>#P</sup> were contained in BPP<sup>NP</sup>, it would imply that PH is contained in BPP<sup>NP</sup>, which would collapse the polynomial hierarchy to the third (or second?) level, which is considered unlikely. </p> <p>In conclusion, P<sup>#P</sup> is considered to be more powerful than NP, BPP, BPP<sup>NP</sup> and even NP<sup>NP<sup>NP</sup></sup>.</p>