Return to Question

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?

Thanks

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

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 either way. So I'm also interested in any results that provide evidence either way.

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

Thanks

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?

Thanks

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. If not, then is $BPP^{NP}$ believed to be equal to #P?

Thanks

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 either way. So I'm also interested in any results that provide evidence either way.

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

Thanks