5
$\begingroup$

Luca Trevisan here gives a randomized polynomial-time approximation algorithm for #3-coloring given an NP oracle.

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).

If there are no such results, then is $BPP^{NP}$ generally believed to be equal to #P?

*Edit: * As per Mariano's suggestion, Here's the Complexity Zoo's excellent description of the complexity class BPP. And here is the description of the complexity class #P.

Thanks

Improve this question
$\endgroup$
13
  • 3
    $\begingroup$ While surely anyone who will be able to answer this will know what BPP is, maybe a very succint description might be of quite some help to us mere humans :P $\endgroup$ Commented Jan 4, 2010 at 18:34
  • 16
    $\begingroup$ Theoretical CS is part of mathematics, and there is no MathOverflow for computer science (SO is more applied), so I think the question fits MO well. Also, the Complexity Zoo Veterinarian is Greg Kuperberg. $\endgroup$ Commented Jan 4, 2010 at 19:01
  • 2
    $\begingroup$ @Anweshi: You think computational complexity theory is not appropriate for MO? Wow. $\endgroup$ Commented Jan 4, 2010 at 23:11
  • 4
    $\begingroup$ Complexity theory in particular is far closer to mathematics than it is to standard CS stuff like programming, compilers, databases, operating systems, etc. As such it is completely appropriate to have complexity theory questions on MO. $\endgroup$ Commented Jan 5, 2010 at 3:04
  • 5
    $\begingroup$ If I were the one asking the question I would be sorely tempted to post in on stackoverflow saying "People at mathoverflow suggested I ask this question here..." :) $\endgroup$ Commented Jan 5, 2010 at 3:23

1 Answer 1

Reset to default
10
$\begingroup$

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.

About your question, BPPNP is contained in PPP and P#P by Toda's theorem. On the other hand, if P#P were contained in BPPNP, it would imply that PH is contained in BPPNP, which would collapse the polynomial hierarchy to the third (or second?) level, which is considered unlikely.

In conclusion, P#P is considered to be more powerful than NP, BPP, BPPNP and even NPNPNP.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.