10
$\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$
  • 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 '12 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 '12 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$ – T.... Nov 21 '17 at 10:59
13
+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$
  • $\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 '12 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 '12 at 5:59
8
$\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$
6
$\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
    $\begingroup$ that's a cool description :) $\endgroup$ – Sasho Nikolov Aug 21 '12 at 16:17
-1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy