<p>In fact, <strong>GenericallyP</strong> = <strong>P</strong>:</p>
<blockquote>
<p><strong>Proposition.</strong> The following are equivalent for any language <span class="math-container">$L$</span>:</p>
<ol>
<li><span class="math-container">$L\in\mathbf P$</span>.</li>
<li><span class="math-container">$L\in\mathbf{GenericallyP}$</span>.</li>
<li><span class="math-container">$\{A\in\{0,1\}^\mathbb N:L\in\mathbf P^A\}$</span> is not meager.</li>
</ol>
</blockquote>
<p><strong>Proof:</strong></p>
<p>Clearly, 1 → 2 → 3.</p>
<p>3 → 1: Let <span class="math-container">$\{M_n:n\in\mathbb N\}$</span> be an enumeration of poly-time oracle machines, and put <span class="math-container">$X_n=\{A\in\{0,1\}^\mathbb N:L(M_n^A)=L\}$</span>.
Observe that <span class="math-container">$X_n$</span> is closed: if <span class="math-container">$A\notin X_n$</span>, we may fix <span class="math-container">$x\in\{0,1\}^*$</span> such that <span class="math-container">$M_n^A$</span> accepts <span class="math-container">$x$</span> and <span class="math-container">$x\notin L$</span>, or vice versa; the computation of <span class="math-container">$M_n^A$</span> on input <span class="math-container">$x$</span> queries the oracle only finitely many times, and any <span class="math-container">$A'$</span> that agrees with <span class="math-container">$A$</span> on these finitely many values will also be outside <span class="math-container">$X_n$</span>.</p>
<p>If <span class="math-container">$\{A\in\{0,1\}^\mathbb N:L\in\mathbf P^A\}=\bigcup_{n\in\mathbb N}X_n$</span> is not meager, there is <span class="math-container">$n$</span> such that <span class="math-container">$X_n$</span> is not nowhere dense. Being closed, this means <span class="math-container">$X_n$</span> has nonempty interior: there is <span class="math-container">$w\in\{0,1\}^*$</span> such that <span class="math-container">$B_w\subseteq X_n$</span>. But then <span class="math-container">$L=L(M_n^w)\in\mathbf P$</span> (using <span class="math-container">$w$</span> itself as a finite oracle).</p>
<hr />
<p>Note that this argument did not use anything special about <strong>P</strong>: the analogous result holds for any class of decision or function problems defined by oracle algorithms (not necessarily Turing machines, and possibly nondeterministic, randomized, or what not) such that the outcome of the computation on any given input is determined by finitely many bits of the oracle, and such that a finite oracle can be hardwired into the algorithm itself. Thus, the title question can be plausibly answered as “pretty much nothing”.</p>
<p>The argument above is reminiscent of a part of the standard proof that <strong>AlmostP</strong> = <strong>BPP</strong>. The principal difference between the two setups that ensures we get a stronger result is that closed (or even Borel) sets can be approximated by open sets up to a meager difference, whereas in the realm of measure, they can only be approximated by open sets up to measure <span class="math-container">$\epsilon$</span> for arbitrarily small <span class="math-container">$\epsilon&gt;0$</span>, not up to measure <span class="math-container">$0$</span>.</p>

CC BY-SA 4.0
2023-11-28T23:12:22.710Z
This completely answers the question for all deterministic complexity classes (as well as simplifying the proof of “fact ②” in the question), but it still remains possible that **GenericallyNP** is larger than **NP**, right? If I follow the same reasoning for nondeterministic oracle machines, the $X_n$ sets you define end up being $G_\delta$, so the proof doesn't carry over AFAICS.
Gro-Tsen
CC BY-SA 4.0
2023-11-29T07:59:12.217Z
It works for NP just the same. The machine still needs only a finite part of the oracle to witness its behaviour on any given input (albeit it is exponential rather than polynomial in case it does not accept), thus $X_n$ is still closed.
Emil Jeřábek
CC BY-SA 4.0
2023-11-29T08:40:58.567Z
I edited the answer to clarify this point. The smallest class I can think of where the argument as such fails is **GenericallyRE** (and classes higher up in the arithmetical hierarchy). Still, the version of the argument in the first revision shows that for any $L\in\mathbf{GenericallyRE}$, there is an oracle TM $M$ such that $\{A:L(M^A)=L\}$ (which is $G_\delta$) is comeager. It follows that $L(M^A)\subseteq L$ for all $A$, and for any $x\in L$, $\{A:x\in L(M^A)\}$ is open dense. Thus, in fact, $L=\{x:\exists w\,x\in L(M^w)\}$ is r.e. So **GenericallyRE** = **RE** after all.
Emil Jeřábek
CC BY-SA 4.0
2023-11-29T09:07:07.017Z
Now thanks to you we have a wonderful fallacious (but perhaps still convincing as a heuristic argument?) proof of $≠$: ⓐ “relative to a generic oracle”, $=^G$ and $=^G$, and ⓑ “relative to a generic oracle”, $^G≠^G$ ([Mehlhorn, “On the size of sets of computable functions” (1973)](https://ieeexplore.ieee.org/document/4569743), theorem 4.6); “thus” $≠$. 
Gro-Tsen
CC BY-SA 4.0
2023-11-29T09:26:29.697Z
(Last comment submitted to the [big list of false proofs](https://mathoverflow.net/a/459385/17064) because I think it's pædagogically instructive.)
Gro-Tsen
CC BY-SA 4.0
2023-11-29T09:40:29.603Z
Awesome. ${}{}{}$
Emil Jeřábek
CC BY-SA 4.0
2023-11-29T11:04:08.680Z
Your proof goes a really long way: for any “reasonable” relativizable classes $\mathcal C$ and $\mathcal D$, if $\mathcal C^A\nsubseteq\mathcal D^A$ for some oracle $A$, then $\mathcal C\nsubseteq\mathcal D$. (Besides the computations in $\mathcal C^A$ and $\mathcal D^A$ being determined by finite parts of the oracle, and $\mathcal C^A$ and $\mathcal D^A$ being invariant under a finite change of $A$, I only need $\mathcal C$ to have a “complete problem” $M$ so that $\mathcal C^A\subseteq\mathcal D^A\iff M^A\in\mathcal D^A$. This makes $\{A:\mathcal C^A\nsubseteq\mathcal D^A\}$ $G_\delta$.)
Emil Jeřábek
CC BY-SA 4.0
2023-11-29T11:10:17.450Z
... The point is that a nonempty $G_\delta$ set invariant under finite changes is comeager.
Emil Jeřábek
CC BY-SA 4.0
2023-11-27T17:21:43.990Z
2023-11-29T08:16:26.160Z
2023-11-29T08:16:26.160Z
Emil Jeřábek
<p>Let me first recall a few (lengthy but hopefully mostly standard) facts and definitions in order to motivate my question (feel free to skip down to the actual question):</p>
<ul>
<li><p><strong>Standard definitions:</strong> A subset <span class="math-container">$N \subseteq \lbrace 0,1\rbrace^{\mathbb{N}}$</span> is said to be <strong>null</strong> (= “of measure <span class="math-container">$0$</span>”) when for all <span class="math-container">$\varepsilon&gt;0$</span> there is a finite-or-infinite sequence <span class="math-container">$(w_n)$</span> of finite words <span class="math-container">$w_n \in \lbrace 0,1\rbrace^ * $</span> such that <span class="math-container">$N \subseteq \bigcup_n B_{w_n}$</span> and <span class="math-container">$\sum_n 2^{-\ell(w_n)} &lt; \varepsilon$</span> where <span class="math-container">$B_{w_n} \subseteq \lbrace 0,1\rbrace^{\mathbb{N}}$</span> denotes the set of binary sequences having <span class="math-container">$w_n$</span> as prefix.  A subset <span class="math-container">$M \subseteq \lbrace 0,1\rbrace^{\mathbb{N}}$</span> is said to be <strong>meager</strong> (= “of first category”) when there is a finite-or-infinite sequence <span class="math-container">$(R_n)$</span> of subsets <span class="math-container">$R_n \subseteq \lbrace 0,1\rbrace^{\mathbb{N}}$</span> such that <span class="math-container">$M \subseteq \bigcup_n R_n$</span> and <span class="math-container">$R_n$</span> is nowhere dense (= “rare”) in the sense that for every finite word <span class="math-container">$w \in \lbrace 0,1\rbrace^ * $</span> there is a finite extension <span class="math-container">$w'$</span> of <span class="math-container">$w$</span> such that <span class="math-container">$B_{w'} \cap R_n = \varnothing$</span>.  We say that a set is <strong>of full measure</strong> when its complement is null, and <strong>comeager</strong> when its complement is meager.</p>
</li>
<li><p>Recall that there is a large amount of parallelism between the two notions: a theme that is explored, for example, in Oxtoby's classic book <em>Measure and Category</em> (1980).  Both “null” and “meager” are notions of smallness, and both are closed under countable unions.  However, they are also in a sense opposed: for example, the set of binary sequences <span class="math-container">$b \in \lbrace 0,1\rbrace^{\mathbb{N}}$</span> such that the average proportion of <span class="math-container">$1$</span>'s in the <span class="math-container">$n$</span> first bits <span class="math-container">$\rho_n := \frac{1}{n}\sum_{k=0}^{n-1} b_k$</span> does not tend to <span class="math-container">$\frac{1}{2}$</span> is null (i.e., from the measure point of view, “almost all” sequences have <span class="math-container">$\lim_n \rho_n = \frac{1}{2}$</span>) whereas that same set is meager (i.e., from the category point of view, “generically all” sequences do <em>not</em> have this property, in fact, on a comeager set, <span class="math-container">$\limsup_n \rho_n = 1$</span> and <span class="math-container">$\liminf_n \rho_n = 0$</span>).  In particular, <span class="math-container">$\lbrace 0,1\rbrace^{\mathbb{N}}$</span> is the union of a null and a meager set.</p>
</li>
<li><p>A perhaps not so well-known <strong>fact ① from computability</strong>: if <span class="math-container">$L \in \lbrace 0,1\rbrace^{\mathbb{N}}$</span> is such that <span class="math-container">$\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \mathrel{\leq_{\mathrm{T}}} A \rbrace$</span> is of full measure (or, indeed, when it is not null), then in fact <span class="math-container">$L$</span> is computable.  Here, <span class="math-container">$\mathrel{\leq_{\mathrm{T}}}$</span> denotes Turing-reducibility (in fact, by countable additivity, we might as well assume that the same oracle machine does the reduction in every case).  In other words, “a non-trivial Turing upper cone is null”.  In other words, “if <span class="math-container">$L$</span> is computable by a non-null set of oracles, then it is computable”.  References for this fact: Sacks, <em>Degrees of Unsolvability</em> (1963), §10, theorem 1 (p. 154); Nies, <em>Computability and Randomness</em> (2009), theorem 5.1.12 (p. 169); or Downey &amp; Hirschfeldt, <em>Algorithmic Randomness and Complexity</em> (2010), corollary 8.2.12 (p. 358).</p>
</li>
<li><p>The dual (and perhaps even less well known) <strong>fact ② from computability</strong>: if <span class="math-container">$L \in \lbrace 0,1\rbrace^{\mathbb{N}}$</span> is such that <span class="math-container">$\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \mathrel{\leq_{\mathrm{T}}} A \rbrace$</span> is comeager (or, indeed, when it is not meager), then in fact <span class="math-container">$L$</span> is computable.  (Again, we might as well assume that the same oracle machine does the reduction in every case.)  In other words, “a non-trivial Turing upper cone is meager”.  In other words, “if <span class="math-container">$L$</span> is computable by a non-meager set of oracles, then it is computable”.  References for this fact: Hinman, <em>Recursion-Theoretic Hierarchies</em> (1978), theorem II.5.3 (p. 63); or Cooper, <em>Computability Theory</em> (2004), example 13.2.21 (p. 283).</p>
</li>
<li><p>If <span class="math-container">$X$</span> is a relativizable complexity class of decision problems, the class <span class="math-container">$\textbf{Almost}X$</span> is defined as the class of decision problems <span class="math-container">$L$</span> such that <span class="math-container">$\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \in X^A \rbrace$</span> is of full measure.  Among the standard identities are the fact that <span class="math-container">$\textbf{AlmostP} = \textbf{BPP}$</span>, <span class="math-container">$\textbf{AlmostNP} = \textbf{AM}$</span> and <span class="math-container">$\textbf{AlmostPSPACE} = \textbf{BP}^{\exp}\,\textbf{PSPACE}$</span>: see <a href="https://blog.computationalcomplexity.org/2023/03/identities-in-computational-complexity.html" rel="noreferrer">this blog post by Josh Grochow</a> for references.  Note that, “fact ①” above can be rephrased as “<span class="math-container">$\textbf{AlmostComputable} = \textbf{Computable}$</span>”.</p>
</li>
</ul>
<p>I'm sure everyone can see where I'm going now:</p>
<ul>
<li><strong>Definition</strong> (mine, non-standard): if <span class="math-container">$X$</span> is a relativizable complexity class of decision problems, define the class <span class="math-container">$\textbf{Generically}X$</span> as the class of decision problems <span class="math-container">$L$</span> such that <span class="math-container">$\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \in X^A \rbrace$</span> is comeager.  Note that, “fact ②” above can be rephrased as “<span class="math-container">$\textbf{GenericallyComputable} = \textbf{Computable}$</span>”.</li>
</ul>
<p>✱ <strong>Warning:</strong> It is tempting to express “<span class="math-container">$\textbf{Almost}X$</span>” as “<span class="math-container">$X$</span> with respect to a random oracle” and “<span class="math-container">$\textbf{Generically}X$</span>” as “<span class="math-container">$X$</span> with respect to a generic oracle”.  (Indeed, this is how I think of them intuitively.)  This is, however, potentially confusing, because there are absolutely defined notions of “random” and “generic”, and in fact many variations on what “random” and “generic” mean (even though the common theme is “does not belong to any computable-in-some-sense null set”, resp. “does not belong to any computable-in-some-sense meager set”).  See <a href="https://cstheory.stackexchange.com/q/25995/17747">this other question</a> and the answers to it concerning “random”, but the same points can be made concerning “generic”.  (In the context of set theory, see Jech, <em>Set Theory (Third Millennium Edition)</em> lemma 26.4 (p. 514) for a characterization of (forcing-)random reals and (Cohen-forcing-)generic reals along these lines.)  So I prefer to refrain speaking of “random” and “generic” oracles in the actual question, but it is also impossible <em>not</em> to make the point, and I took the liberty to use it in the “generic oracle” terminology in the title of the question.</p>
<p><strong>QUESTIONS:</strong> Having defined <span class="math-container">$\textbf{GenericallyP}$</span> as the class of decision problems <span class="math-container">$L$</span> such that <span class="math-container">$\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \in \textbf{P}^A \rbrace$</span> is comeager, let me ask the following:</p>
<ul>
<li><p>Is <span class="math-container">$\textbf{GenericallyP}$</span> equal to a standard complexity class (e.g., one in the Complexity Zoo)?  Has it received another name?  Has it been studied?  Can we say anything non-trivial about it?</p>
</li>
<li><p>Can we identify a problem in <span class="math-container">$\textbf{GenericallyP}$</span> that is conjecturally not not in <span class="math-container">$\textbf{P}$</span>, or even “not obviously” in <span class="math-container">$\textbf{P}$</span>?  Or is it reasonable to conjecture that <span class="math-container">$\textbf{GenericallyP} = \textbf{P}$</span>?</p>
</li>
<li><p>Soft question: intuitively speaking, what might a “pseudogeneric” sequence generator even look like?  (I can make some sense of “pseudorandom” because randomness lends itself quite well to finite approximations, but “pseudogeneric” seems much more slippery: as noted above, whereas pseudorandom sequences obey the law of large numbers, pseudogeneric ones avoid all such laws.  And conversely, whereas I can imagine how to make <em>use</em> of a random oracle, making use of a generic oracle seems almost unthinkable: but I'd be happy to be proved wrong here.)</p>
</li>
</ul>

<cc.complexity-theory><complexity-classes><oracles>
What can we do with a generic oracle (as opposed to a random one)?
Gro-Tsen
# What can we do with a generic oracle (as opposed to a random one)?

(Asked by: username_0 on 2023-11-27)

Let me first recall a few (lengthy but hopefully mostly standard) facts and definitions in order to motivate my question (feel free to skip down to the actual question):

* **Standard definitions:** A subset $N \subseteq \lbrace 0,1\rbrace^{\mathbb{N}}$ is said to be **null** (= “of measure $0$”) when for all $\varepsilon>0$ there is a finite-or-infinite sequence $(w\_n)$ of finite words $w\_n \in \lbrace 0,1\rbrace^ \* $ such that $N \subseteq \bigcup\_n B\_{w\_n}$ and $\sum\_n 2^{-\ell(w\_n)} < \varepsilon$ where $B\_{w\_n} \subseteq \lbrace 0,1\rbrace^{\mathbb{N}}$ denotes the set of binary sequences having $w\_n$ as prefix. A subset $M \subseteq \lbrace 0,1\rbrace^{\mathbb{N}}$ is said to be **meager** (= “of first category”) when there is a finite-or-infinite sequence $(R\_n)$ of subsets $R\_n \subseteq \lbrace 0,1\rbrace^{\mathbb{N}}$ such that $M \subseteq \bigcup\_n R\_n$ and $R\_n$ is nowhere dense (= “rare”) in the sense that for every finite word $w \in \lbrace 0,1\rbrace^ \* $ there is a finite extension $w'$ of $w$ such that $B\_{w'} \cap R\_n = \varnothing$. We say that a set is **of full measure** when its complement is null, and **comeager** when its complement is meager.
* Recall that there is a large amount of parallelism between the two notions: a theme that is explored, for example, in Oxtoby's classic book *Measure and Category* (1980). Both “null” and “meager” are notions of smallness, and both are closed under countable unions. However, they are also in a sense opposed: for example, the set of binary sequences $b \in \lbrace 0,1\rbrace^{\mathbb{N}}$ such that the average proportion of $1$'s in the $n$ first bits $\rho\_n := \frac{1}{n}\sum\_{k=0}^{n-1} b\_k$ does not tend to $\frac{1}{2}$ is null (i.e., from the measure point of view, “almost all” sequences have $\lim\_n \rho\_n = \frac{1}{2}$) whereas that same set is meager (i.e., from the category point of view, “generically all” sequences do *not* have this property, in fact, on a comeager set, $\limsup\_n \rho\_n = 1$ and $\liminf\_n \rho\_n = 0$). In particular, $\lbrace 0,1\rbrace^{\mathbb{N}}$ is the union of a null and a meager set.
* A perhaps not so well-known **fact ① from computability**: if $L \in \lbrace 0,1\rbrace^{\mathbb{N}}$ is such that $\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \mathrel{\leq\_{\mathrm{T}}} A \rbrace$ is of full measure (or, indeed, when it is not null), then in fact $L$ is computable. Here, $\mathrel{\leq\_{\mathrm{T}}}$ denotes Turing-reducibility (in fact, by countable additivity, we might as well assume that the same oracle machine does the reduction in every case). In other words, “a non-trivial Turing upper cone is null”. In other words, “if $L$ is computable by a non-null set of oracles, then it is computable”. References for this fact: Sacks, *Degrees of Unsolvability* (1963), §10, theorem 1 (p. 154); Nies, *Computability and Randomness* (2009), theorem 5.1.12 (p. 169); or Downey & Hirschfeldt, *Algorithmic Randomness and Complexity* (2010), corollary 8.2.12 (p. 358).
* The dual (and perhaps even less well known) **fact ② from computability**: if $L \in \lbrace 0,1\rbrace^{\mathbb{N}}$ is such that $\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \mathrel{\leq\_{\mathrm{T}}} A \rbrace$ is comeager (or, indeed, when it is not meager), then in fact $L$ is computable. (Again, we might as well assume that the same oracle machine does the reduction in every case.) In other words, “a non-trivial Turing upper cone is meager”. In other words, “if $L$ is computable by a non-meager set of oracles, then it is computable”. References for this fact: Hinman, *Recursion-Theoretic Hierarchies* (1978), theorem II.5.3 (p. 63); or Cooper, *Computability Theory* (2004), example 13.2.21 (p. 283).
* If $X$ is a relativizable complexity class of decision problems, the class $\textbf{Almost}X$ is defined as the class of decision problems $L$ such that $\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \in X^A \rbrace$ is of full measure. Among the standard identities are the fact that $\textbf{AlmostP} = \textbf{BPP}$, $\textbf{AlmostNP} = \textbf{AM}$ and $\textbf{AlmostPSPACE} = \textbf{BP}^{\exp}\,\textbf{PSPACE}$: see [this blog post by Josh Grochow](https://blog.computationalcomplexity.org/2023/03/identities-in-computational-complexity.html) for references. Note that, “fact ①” above can be rephrased as “$\textbf{AlmostComputable} = \textbf{Computable}$”.

I'm sure everyone can see where I'm going now:

* **Definition** (mine, non-standard): if $X$ is a relativizable complexity class of decision problems, define the class $\textbf{Generically}X$ as the class of decision problems $L$ such that $\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \in X^A \rbrace$ is comeager. Note that, “fact ②” above can be rephrased as “$\textbf{GenericallyComputable} = \textbf{Computable}$”.

✱ **Warning:** It is tempting to express “$\textbf{Almost}X$” as “$X$ with respect to a random oracle” and “$\textbf{Generically}X$” as “$X$ with respect to a generic oracle”. (Indeed, this is how I think of them intuitively.) This is, however, potentially confusing, because there are absolutely defined notions of “random” and “generic”, and in fact many variations on what “random” and “generic” mean (even though the common theme is “does not belong to any computable-in-some-sense null set”, resp. “does not belong to any computable-in-some-sense meager set”). See [this other question](https://cstheory.stackexchange.com/q/25995/17747) and the answers to it concerning “random”, but the same points can be made concerning “generic”. (In the context of set theory, see Jech, *Set Theory (Third Millennium Edition)* lemma 26.4 (p. 514) for a characterization of (forcing-)random reals and (Cohen-forcing-)generic reals along these lines.) So I prefer to refrain speaking of “random” and “generic” oracles in the actual question, but it is also impossible *not* to make the point, and I took the liberty to use it in the “generic oracle” terminology in the title of the question.

**QUESTIONS:** Having defined $\textbf{GenericallyP}$ as the class of decision problems $L$ such that $\lbrace A \in \lbrace 0,1\rbrace^{\mathbb{N}} : L \in \textbf{P}^A \rbrace$ is comeager, let me ask the following:

* Is $\textbf{GenericallyP}$ equal to a standard complexity class (e.g., one in the Complexity Zoo)? Has it received another name? Has it been studied? Can we say anything non-trivial about it?
* Can we identify a problem in $\textbf{GenericallyP}$ that is conjecturally not not in $\textbf{P}$, or even “not obviously” in $\textbf{P}$? Or is it reasonable to conjecture that $\textbf{GenericallyP} = \textbf{P}$?
* Soft question: intuitively speaking, what might a “pseudogeneric” sequence generator even look like? (I can make some sense of “pseudorandom” because randomness lends itself quite well to finite approximations, but “pseudogeneric” seems much more slippery: as noted above, whereas pseudorandom sequences obey the law of large numbers, pseudogeneric ones avoid all such laws. And conversely, whereas I can imagine how to make *use* of a random oracle, making use of a generic oracle seems almost unthinkable: but I'd be happy to be proved wrong here.)

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


---

## 1 answers

### Answer by username_1 on 2023-11-27. Score: 9 | Accepted answer

In fact, **GenericallyP** = **P**:

> **Proposition.** The following are equivalent for any language $L$:
>
> 1. $L\in\mathbf P$.
> 2. $L\in\mathbf{GenericallyP}$.
> 3. $\{A\in\{0,1\}^\mathbb N:L\in\mathbf P^A\}$ is not meager.

**Proof:**

Clearly, 1 → 2 → 3.

3 → 1: Let $\{M\_n:n\in\mathbb N\}$ be an enumeration of poly-time oracle machines, and put $X\_n=\{A\in\{0,1\}^\mathbb N:L(M\_n^A)=L\}$.
Observe that $X\_n$ is closed: if $A\notin X\_n$, we may fix $x\in\{0,1\}^\*$ such that $M\_n^A$ accepts $x$ and $x\notin L$, or vice versa; the computation of $M\_n^A$ on input $x$ queries the oracle only finitely many times, and any $A'$ that agrees with $A$ on these finitely many values will also be outside $X\_n$.

If $\{A\in\{0,1\}^\mathbb N:L\in\mathbf P^A\}=\bigcup\_{n\in\mathbb N}X\_n$ is not meager, there is $n$ such that $X\_n$ is not nowhere dense. Being closed, this means $X\_n$ has nonempty interior: there is $w\in\{0,1\}^\*$ such that $B\_w\subseteq X\_n$. But then $L=L(M\_n^w)\in\mathbf P$ (using $w$ itself as a finite oracle).

---

Note that this argument did not use anything special about **P**: the analogous result holds for any class of decision or function problems defined by oracle algorithms (not necessarily Turing machines, and possibly nondeterministic, randomized, or what not) such that the outcome of the computation on any given input is determined by finitely many bits of the oracle, and such that a finite oracle can be hardwired into the algorithm itself. Thus, the title question can be plausibly answered as “pretty much nothing”.

The argument above is reminiscent of a part of the standard proof that **AlmostP** = **BPP**. The principal difference between the two setups that ensures we get a stronger result is that closed (or even Borel) sets can be approximated by open sets up to a meager difference, whereas in the realm of measure, they can only be approximated by open sets up to measure $\epsilon$ for arbitrarily small $\epsilon>0$, not up to measure $0$.

> **Comments:**
> **username_0**: This completely answers the question for all deterministic complexity classes (as well as simplifying the proof of “fact ②” in the question), but it still remains possible that **GenericallyNP** is larger than **NP**, right? If I follow the same reasoning for nondeterministic oracle machines, the $X_n$ sets you define end up being $G_\delta$, so the proof doesn't carry over AFAICS.  
> **username_1**: It works for NP just the same. The machine still needs only a finite part of the oracle to witness its behaviour on any given input (albeit it is exponential rather than polynomial in case it does not accept), thus $X_n$ is still closed.  
> **username_1**: I edited the answer to clarify this point. The smallest class I can think of where the argument as such fails is **GenericallyRE** (and classes higher up in the arithmetical hierarchy). Still, the version of the argument in the first revision shows that for any $L\in\mathbf{GenericallyRE}$, there is an oracle TM $M$ such that $\{A:L(M^A)=L\}$ (which is $G_\delta$) is comeager. It follows that $L(M^A)\subseteq L$ for all $A$, and for any $x\in L$, $\{A:x\in L(M^A)\}$ is open dense. Thus, in fact, $L=\{x:\exists w\,x\in L(M^w)\}$ is r.e. So **GenericallyRE** = **RE** after all.  
> **username_0**: Now thanks to you we have a wonderful fallacious (but perhaps still convincing as a heuristic argument?) proof of $≠$: ⓐ “relative to a generic oracle”, $=^G$ and $=^G$, and ⓑ “relative to a generic oracle”, $^G≠^G$ ([Mehlhorn, “On the size of sets of computable functions” (1973)](https://ieeexplore.ieee.org/document/4569743), theorem 4.6); “thus” $≠$.   
> **username_0**: (Last comment submitted to the [big list of false proofs](https://mathoverflow.net/a/459385/17064) because I think it's pædagogically instructive.)  
> **username_1**: Awesome. ${}{}{}$  
> **username_1**: Your proof goes a really long way: for any “reasonable” relativizable classes $\mathcal C$ and $\mathcal D$, if $\mathcal C^A\nsubseteq\mathcal D^A$ for some oracle $A$, then $\mathcal C\nsubseteq\mathcal D$. (Besides the computations in $\mathcal C^A$ and $\mathcal D^A$ being determined by finite parts of the oracle, and $\mathcal C^A$ and $\mathcal D^A$ being invariant under a finite change of $A$, I only need $\mathcal C$ to have a “complete problem” $M$ so that $\mathcal C^A\subseteq\mathcal D^A\iff M^A\in\mathcal D^A$. This makes $\{A:\mathcal C^A\nsubseteq\mathcal D^A\}$ $G_\delta$.)  
> **username_1**: ... The point is that a nonempty $G_\delta$ set invariant under finite changes is comeager.  

---

