8
$\begingroup$

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

$\endgroup$

1 Answer 1

8
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 29, 2023 at 7:59
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 29, 2023 at 8:40
  • 1
    $\begingroup$ 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), theorem 4.6); “thus” $𝐏≠𝐍𝐏$. 🙃 $\endgroup$
    – Gro-Tsen
    Nov 29, 2023 at 9:07
  • 1
    $\begingroup$ 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$.) $\endgroup$ Nov 29, 2023 at 11:04
  • 1
    $\begingroup$ ... The point is that a nonempty $G_\delta$ set invariant under finite changes is comeager. $\endgroup$ Nov 29, 2023 at 11:10

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .