10
$\begingroup$

Let $G$ be a generic oracle in the sense of Cohen / Baire category. Let $R$ be a random oracle.

Are there complexity classes A and B with $$\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^R$$ or the other way around, $$\mathrm{A}^G\ne\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R= \mathrm{B}^R\text{?}$$

The question was inspired by a comment by Scott Aaronson.

$\endgroup$
11
$\begingroup$

P = UP with a generic (assuming P = PSPACE) but they are separate relative to a random oracle.

In the other direction P = Promise-BPP relative to a random but separate relative to a generic. Can't think of a non-promise class off the top of my head.

I can track down some references if you need.

Update: If you want a non-promise version, $P^{NP} = S^p_2$ with a random oracle (because $S^p_2 \subseteq ZPP^{NP}$) but they separate with a generic oracle (example in my paper with Yamakami).

$\endgroup$
  • 3
    $\begingroup$ P=PSPACE seems like a bold assumption ;) $\endgroup$ – Bjørn Kjos-Hanssen Sep 11 '17 at 23:05
  • 4
    $\begingroup$ To clarify Bjorn's comment: another way to phrase it is to first relativize to a PSPACE oracle, then build a generic, and then you get P=UP. So there is a (relative-to-PSPACE-)generic oracle that makes P=UP. $\endgroup$ – Joshua Grochow Sep 12 '17 at 16:28
  • $\begingroup$ I added a non-promise example. Also you need to make some assumption because if P $\neq$ UP in the nonrelativized world then they remain different relative to a generic. Or you can use Josh's trick. $\endgroup$ – Lance Fortnow Sep 13 '17 at 17:02
3
$\begingroup$

I do not think we know of unconditional uniform/nonpromise complexity class differences in the above form (update: see Lance Fortnow's answer for an example), but the following comparison of generic oracles to random oracles may be helpful.

A generic oracle is by construction an oracle that satisfies every $Σ^0_1$ property that cannot be ruled out by fixing a finite initial segment. In a certain sense, everything that is necessarily possible happens, which makes it very different from a random oracle (though it also emulates a random oracle infinitely often).

For example, with the generic oracle (i.o. means infinitely often)
PSPACE ⊆ i.o.-P
EXP ⊆ i.o-ZPP
EXPNP ⊆ i.o-BPP

Thus, for every problem in the relativized PSPACE, there is a polynomial time algorithm (using the oracle) that for infinitely many input sizes solves all instances of that size (and similarly with ZPP and BPP with arbitrary behavior at 'bad' input sizes).

Like the random oracle:
IP < PSPACE
The polynomial hierarchy is infinite.

Every recursive function computable in polynomial time with a generic oracle is computable in polynomial time without the oracle (since the oracle is empty for sufficiently long stretches). Thus, if P < BPP, then this also holds for the generic oracle, while for the random oracle P = BPP.

$\endgroup$
  • $\begingroup$ What do you mean by =i.o. between classes of languages? $\endgroup$ – Kaveh Sep 12 '17 at 0:39
  • 1
    $\begingroup$ So, by "P = i.o.PSPACE" you actually mean PSPACE $\subseteq$ i.o.P? That's quite confusing. Why did you move the i.o. prefix to the other class? $\endgroup$ – Emil Jeřábek Sep 12 '17 at 6:37
  • $\begingroup$ @Kaveh A =i.o. B means there is an infinite set S such that A ⊆ S-B and B ⊆ S-A (where S-B is defined analogously to i.o.-B). However, since this usage is nonstandard, I changed my answer to use ⊆ i.o. $\endgroup$ – Dmytro Taranovsky Sep 12 '17 at 15:18
  • $\begingroup$ @EmilJeřábek I replaced =i.o. with the standard ⊆ i.o. $\endgroup$ – Dmytro Taranovsky Sep 12 '17 at 15:21
  • $\begingroup$ I know what it means for languages, I am asking what it means for classes of languages. i.o.-C makes sense for a class C, =i.o. as a relation doesn't seem to make sense as you originally wrote. $\endgroup$ – Kaveh Sep 12 '17 at 18:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.