Depth Relative to K-Trivial Oracles

Definitions and mathematical statement

Identify an oracle $A\subseteq{\mathbb{N}}$ with its characteristic sequence in $2^{{\mathbb{N}}}$, where ${\mathbb{N}}=\{0,1,2,\ldots\}$. Fix an optimal prefix-free machine, and let $K(\sigma)$ denote the prefix-free Kolmogorov complexity of a finite binary string $\sigma$. Write $K(n)$ for the complexity of a fixed effective encoding of $n$. The oracle $A$ is $K$-trivial if \[ \exists c\in{\mathbb{N}}\ \forall n\in{\mathbb{N}}\qquad K(A\upharpoonright n)\leq K(n)+c, \] where $A\upharpoonright n$ is its initial segment of length $n$.

Let $\mathcal D\subseteq 2^{{\mathbb{N}}}$ denote the class of deep sequences intended by the source, and let $\mathcal D^{A}\subseteq 2^{{\mathbb{N}}}$ denote its intended class of sequences that are deep relative to $A$. These are provisional predicate names: the supplied record does not define depth or its relativization. In particular, it does not specify the underlying complexity convention, the time bounds, or the quantifier pattern in the depth condition. Those definitions must be recovered from the supplied references before this becomes a fully specified mathematical problem.

Source question. For each $K$-trivial oracle $A$, determine whether \[ \mathcal D^{A}\subsetneq\mathcal D \qquad\text{or}\qquad \mathcal D^{A}=\mathcal D. \] Here the reading of "$A$-depth is strictly stronger than depth" is \[ \left(\forall X\in 2^{{\mathbb{N}}}\;[X\in\mathcal D^{A}\Rightarrow X\in\mathcal D]\right) \ \land\ \left(\exists X\in 2^{{\mathbb{N}}}\;[X\in\mathcal D\land X\notin\mathcal D^{A}]\right), \] and coincidence means \[ \forall X\in 2^{{\mathbb{N}}}\qquad X\in\mathcal D^{A}\Longleftrightarrow X\in\mathcal D. \] More generally, characterize the $K$-trivial oracles satisfying each of these two comparisons. The alternatives preserve the source's formulation; this draft does not establish the inclusion or assert that the alternatives are exhaustive. The intended depth definitions and any hypotheses supporting that dichotomy remain unresolved.

Short English statement

For each $K$-trivial oracle $A$, determine whether depth relative to $A$ is a strictly stronger property than ordinary depth or is the same property, and characterize which oracles give each outcome. The supplied record leaves the precise depth definitions unspecified, so this is a conditional formulation requiring source verification and human mathematical review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004669$, titled "Depth Relative to K-Trivial Oracles," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual problem proposer is named. The supplied status is "open." The supplied label corrected_verified is accompanied by an editorial verification note stating that only formula delimiters, notation, grammar, and typography were repaired while mathematical content and scope were preserved; it is not an independent mathematical verification here.
• Supplied report citation: Computability Theory (2022), Oberwolfach Reports, DOI 10.4171/owr/2021/21, pp. 1149--1190. https://doi.org/10.4171/owr/2021/21. The record separately gives proposed year 2021 and describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Delle Rose, Bienvenu and Merkle, Relativized depth. Supplied literature reference: https://iris.uniroma1.it/bitstream/11573/1713789/1/relativized-depth.pdf.
• Oberwolfach Report 21/2021. Supplied literature reference: https://ems.press/content/serial-article-files/46899.
• Supplied literature assessment checked on 2026-08-22: status "open"; relativized depth has been developed and its basic preservation theorems proved, while the central alternatives for $K$-trivial oracles are explicitly left open. This is supplied dated curation derived from the OWR material, not an independently verified assessment. The record expressly requests independent verification of time-sensitive status and cited claims.