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?

Improve this question
$\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$
    – Robin Kothari
    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$
    – Sajin Koroth
    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
    Nov 21, 2017 at 10:59

4 Answers 4

Reset to default
16
+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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ here is the free download link from citeseer citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1232 $\endgroup$
    – Marcos Villagra
    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$
    – Robin Kothari
    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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ that's a cool description :) $\endgroup$
    – Sasho Nikolov
    Aug 21, 2012 at 16:17
0
$\begingroup$

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

Improve this answer
$\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$
    – Robin Kothari
    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$
    – Luke Mathieson
    Aug 21, 2012 at 3:41
  • $\begingroup$ Quite right, they only show the $BPP^{A} = P^{A}$ case. My mistake. $\endgroup$
    – Luke Mathieson
    Aug 24, 2012 at 4:50

Your Answer

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