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