12
$\begingroup$

Let $A$ be any EXP complete problem. Then, $P^A = NP^A$.

Let $B$ be some oracle that takes into accounts the queries that $M$ (a TM in P) will make, and we can get $P^B \neq NP^B$.

Question: Do we have similar oracle results for P vs BPP?

$\endgroup$
3
  • 2
    $\begingroup$ Yes we do, but I'm not sure I can find a citation. (Well the first part is easy, give both classes an oracle for an EXP-complete problem.) $\endgroup$ Commented Jun 26, 2012 at 4:06
  • 3
    $\begingroup$ If you think of PCP setting as verifier having oracle access to prover (where the oracle query $i$ would return the $i^{th}$ bit of the proof) then we know that if you allow verifier to be a BPP machine with $\log n$ randomness and $3$ queries then the class of languages computed is $NP$ and when the verifier is a P machine (that is no randomness) with $3$ (even with $\log n$) queries then the class of languages computed is $\bf P$. This doesn't show an oracle separation unless $\bf P \neq \bf NP$. But just an example where oracle access to $\bf BPP$ "seems" more powerful. $\endgroup$ Commented Jun 26, 2012 at 15:02
  • $\begingroup$ @RobinKothari Let $\oplus P=NP=EXP$ then if $A$ is any $EXP$ complete problem don't we have $NP^A=NP^{\oplus P}=\oplus P^{\oplus P}=\oplus P=NP=EXP\neq P$ (last inequality by time hierarchy)? Then does $P^A=NP^A\implies P^{\oplus P}=NP=\oplus P$ while $P\neq NP$ is shown? $\endgroup$
    – Turbo
    Commented Nov 21, 2017 at 10:59

4 Answers 4

17
+50
$\begingroup$

I had a vague recollection that I knew an excellent reference for such oracle separations. I finally found it.

A great reference for oracle separations (for classes between P and PSPACE) is the following paper:

Vereshchagin, N K (1994), "RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS", Russian Academy of Sciences. Izvestiya Mathematics 42 (2): 261

The paper shows (or gives a citation for) an oracle separation between almost every pair of classes that you might care about between P and PSPACE (e.g., it has classes like P, RP, BPP, UP, FewP, NP, MA, AM, other levels of PH, PH, IP, PSPACE, etc.).

For example, Theorem 8 shows an oracle problem in coRP that is not in NP. Since (relative to all oracles) coRP is in BPP and NP contains P, we get an oracle problem in BPP that is not in P.

As I mentioned in my comment, showing an oracle for which $\text{P}^A = \text{BPP}^A$ is easy. Let A be a EXP-complete language or a PSPACE-complete language.

$\endgroup$
2
  • $\begingroup$ here is the free download link from citeseer citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1232 $\endgroup$ Commented Aug 21, 2012 at 3:52
  • $\begingroup$ Although if you can get the full version, I would recommend that instead. The citeseer version doesn't have figures and is therefore missing a nice complexity class inclusion diagram (Fig 1). $\endgroup$ Commented Aug 21, 2012 at 5:59
10
$\begingroup$

The complexity zoo is your friend! As Robin said, you have half the answer: any EXP-complete problem collapses NP to P, and therefore BPP to P. Buhrman and Fortnow constructed an oracle relative to which P = RP but BPP is not equal to P. This is more than what you asked for; I suspect there are easier constructions that separate P from both RP and BPP.

$\endgroup$
9
$\begingroup$

A nice description of an oracle that separates P and BPP is given by Greg Kuperberg in one of the comments of this interesting blog post, where Terence Tao describes Turing machines with oracles and complexity results relative to oracles in the form of an allegory.

$\endgroup$
1
  • 1
    $\begingroup$ that's a cool description :) $\endgroup$ Commented Aug 21, 2012 at 16:17
0
$\begingroup$

Bennett & Gill give oracles for both cases: http://epubs.siam.org/doi/abs/10.1137/0210008

$\endgroup$
3
  • $\begingroup$ Do they give an oracle to separate BPP from P? I wasn't able to find such a claim in the paper. $\endgroup$ Commented Aug 21, 2012 at 2:16
  • $\begingroup$ I had thought so, unfortunately I'm away from my office so haven't got access to the pdf. I'll have to check later. $\endgroup$ Commented Aug 21, 2012 at 3:41
  • $\begingroup$ Quite right, they only show the $BPP^{A} = P^{A}$ case. My mistake. $\endgroup$ Commented Aug 24, 2012 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.