<p>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.</p>

<p>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).</p>

<p>For example, with the generic oracle (i.o. means infinitely often)<br/>
PSPACE ⊆ i.o.-P <br/>
EXP ⊆ i.o-ZPP <br/>
EXP<sup>NP</sup> ⊆ i.o-BPP<br/></p>

<p>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).</p>

<p>Like the random oracle:<br/>
IP &lt; PSPACE<br/>
The polynomial hierarchy is infinite.</p>

<p>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 &lt; BPP, then this also holds for the generic oracle, while for the random oracle P = BPP.</p>

CC BY-SA 3.0
2017-09-12T00:39:18.317Z
What do you mean by =i.o. between classes of languages?
Kaveh
CC BY-SA 3.0
2017-09-12T06:37:17.760Z
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?
Emil Jeřábek
CC BY-SA 3.0
2017-09-12T15:18:49.443Z
@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.
Dmytro Taranovsky
CC BY-SA 3.0
2017-09-12T15:21:00.143Z
@EmilJeřábek I replaced =i.o. with the standard ⊆ i.o.
Dmytro Taranovsky
CC BY-SA 3.0
2017-09-12T18:41:23.737Z
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.
Kaveh
CC BY-SA 3.0
2017-09-12T19:56:44.467Z
@Kaveh I should have used '⊆ i.o.-' originally, but the construction I meant is the following.  For a set of input lengths S, let S-ZPP consist of problems for which there is a randomized algorithm that for inputs with length in S is polynomial time with zero error (and unlikely failure).  One can similarly define S-EXP, and analogously with other complexity classes; and by ZPP =i.o. EXP, I meant existence of an infinite S such that S-ZPP = S-EXP.
Dmytro Taranovsky
CC BY-SA 3.0
2017-09-13T04:21:34.980Z
I'm just super impressed with your knowledge of structural complexity.  :)
Michael Wehar
CC BY-SA 3.0
2017-09-11T23:59:01.303Z
2017-09-13T21:50:14.133Z
2017-09-13T21:50:14.133Z
Dmytro Taranovsky
<p>P = UP with a generic (assuming P = PSPACE) but they are separate relative to a random oracle.</p>

<p>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.</p>

<p>I can track down some references if you need.</p>

<p>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 <a href="https://doi.org/10.1006/jcss.1996.0015" rel="noreferrer">paper with Yamakami</a>).</p>

CC BY-SA 3.0
2017-09-11T23:05:29.910Z
P=PSPACE seems like a bold assumption ;)
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-09-12T16:28:26.487Z
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.
Joshua Grochow
CC BY-SA 3.0
2017-09-13T17:02:36.847Z
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.
Lance Fortnow
CC BY-SA 3.0
2017-09-11T22:54:56.077Z
2017-09-13T17:01:12.203Z
2017-09-13T17:01:12.203Z
Lance Fortnow
<p>Let $G$ be a generic oracle in the sense of Cohen / Baire category.
Let $R$ be a random oracle.</p>

<p>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{?}$$</p>

<p>The question was inspired by <a href="https://www.scottaaronson.com/blog/?p=3427#comment-1744031" rel="noreferrer">a comment by Scott Aaronson</a>.</p>

<cc.complexity-theory><complexity-classes>
Example of something that’s different for generic and random oracles?
Bjørn Kjos-Hanssen
# Example of something that’s different for generic and random oracles?

(Asked by: username_0 on 2017-09-11)

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](https://www.scottaaronson.com/blog/?p=3427#comment-1744031).

**Tags:** cc.complexity-theory, complexity-classes

---

## 2 answers

### Answer by username_5 on 2017-09-11. Score: 12 | Accepted answer

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](https://doi.org/10.1006/jcss.1996.0015)).

> **Comments:**
> **username_0**: P=PSPACE seems like a bold assumption ;)  
> **username_6**: 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.  
> **username_5**: 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.  

---

### Answer by username_1 on 2017-09-11. Score: 4

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.

> **Comments:**
> **username_2**: What do you mean by =i.o. between classes of languages?  
> **username_3**: 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?  
> **username_1**: @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.  
> **username_1**: @EmilJeřábek I replaced =i.o. with the standard ⊆ i.o.  
> **username_2**: 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.  
> **username_1**: @Kaveh I should have used '⊆ i.o.-' originally, but the construction I meant is the following.  For a set of input lengths S, let S-ZPP consist of problems for which there is a randomized algorithm that for inputs with length in S is polynomial time with zero error (and unlikely failure).  One can similarly define S-EXP, and analogously with other complexity classes; and by ZPP =i.o. EXP, I meant existence of an infinite S such that S-ZPP = S-EXP.  
> **username_4**: I'm just super impressed with your knowledge of structural complexity.  :)  

---

