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.
No comments:
Post a Comment