12
$\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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\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).

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ P=PSPACE seems like a bold assumption ;) $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Sep 11, 2017 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
    Commented Sep 12, 2017 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
    Commented Sep 13, 2017 at 17:02
4
$\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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ What do you mean by =i.o. between classes of languages? $\endgroup$
    – Kaveh
    Commented Sep 12, 2017 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
    Commented Sep 12, 2017 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
    Commented Sep 12, 2017 at 15:18
  • $\begingroup$ @EmilJeřábek I replaced =i.o. with the standard ⊆ i.o. $\endgroup$
    – Dmytro Taranovsky
    Commented Sep 12, 2017 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
    Commented Sep 12, 2017 at 18:41

Your Answer

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

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