Weihrauch Determinacy and Degree Structure Questions

Definitions and mathematical statement

The supplied record bundles three groups of questions. Several terms and one requested property are not defined in the record; the corresponding qualifications below remain unresolved.

1. Weihrauch relations. For multivalued problems on represented spaces, write $f\leq_{\mathrm W}g$ for ordinary Weihrauch reducibility: there are computable preprocessing and postprocessing procedures which, from any input to $f$, produce an input to $g$ and transform any valid answer to that instance, together with the original input, into a valid answer to $f$. Determine, for every ordered pair $(P,Q)$ from \[ \mathcal P=\left\{ \Sigma^0_1\text{-DS},\; \Sigma^0_1\text{-BSLQO},\; \Sigma^0_1\text{-BSPO},\; \Sigma^0_1\text{-BS},\; \Delta^0_2\text{-DS} \right\}, \] whether $P\leq_{\mathrm W}Q$. The source does not define these five problems, their input and output representations, or the meaning of the complexity prefixes for their presentations. Thus this specifies the requested comparison task, but does not yet specify five fully defined represented problems.

2. Determinacy and choice. For definiteness in explaining the notation, code reals by elements of $2^{{\mathbb{N}}}$. Write $x\leq_T y$ for Turing reducibility and $x\equiv_T y$ for mutual Turing reducibility. A set $B\subseteq2^{{\mathbb{N}}}$ is Turing invariant if membership is constant on Turing degrees. A Turing cone is a set \[ C_z=\{x\in2^{{\mathbb{N}}}:z\leq_T x\}. \] The usual cone formulation of Turing determinacy, denoted $\mathsf{TD}$, says that for every Turing-invariant $B\subseteq2^{{\mathbb{N}}}$, some $C_z$ is contained in $B$ or in $2^{{\mathbb{N}}}\setminus B$. Dependent choice for reals, denoted $\mathsf{DC}_{{\mathbb{R}}}$, asserts that for every nonempty $X\subseteq2^{{\mathbb{N}}}$, every relation $R\subseteq X\times X$ satisfying \[ (\forall x\in X)(\exists y\in X)\;xRy, \] and every $a\in X$, there is a sequence $(x_n)_{n\in{\mathbb{N}}}$ in $X$ with $x_0=a$ and $x_nRx_{n+1}$ for every $n$. Full dependent choice, $\mathsf{DC}$, is the corresponding principle for arbitrary nonempty sets $X$.

   The questions are whether \[ \mathsf{TD}\Longrightarrow\mathsf{DC}_{{\mathbb{R}}} \qquad\text{and}\qquad \mathsf{TD}+\mathsf{DC}\Longrightarrow\mathsf{sTD}, \] where $\mathsf{sTD}$ denotes the source's intended strong Turing determinacy principle. The source supplies neither a definition of $\mathsf{sTD}$ nor the background set theory over which either implication is asked. The cone formulation and real coding above explain conventional notation; their agreement with the intended source conventions requires review. The second implication retains the source's unqualified dependent choice.

3. Degree extension questions. A set $B\subseteq{\mathbb{N}}$ is computably enumerable (c.e.) if an algorithm enumerates its elements. A set is $2$-c.e. if it is the difference of two c.e. sets. Write $\deg_T(B)$ for its Turing degree, and order degrees by the reducibility of representatives. In particular, $D\leq_T A$ abbreviates $D\leq_T\deg_T(A)$, and $W\leq_T D$ abbreviates $\deg_T(W)\leq_T D$.

   For every properly $2$-c.e. degree $D$, is it true that \[ \begin{aligned} \exists A\subseteq{\mathbb{N}}\;\bigl[\;&A\text{ is c.e.} \;\land\;D\not\leq_T\deg_T(A)\\ &\land\;(\forall W\subseteq{\mathbb{N}})\bigl( [W\text{ is c.e.}\;\land\;\deg_T(W)\leq_T D] \Longrightarrow W\leq_T A\bigr)\bigr]? \end{aligned} \] A usual degree-level meaning of "properly $2$-c.e." is that $D$ contains a $2$-c.e. set but contains no c.e. set; the supplied record does not explicitly state this convention. Properness of an individual representative alone would be a different condition.

   A c.e. degree is superlow if it has a c.e. representative $B$ whose Turing jump satisfies $B'\leq_{\mathrm{tt}}\varnothing'$, where $\leq_{\mathrm{tt}}$ denotes truth-table reducibility and $\varnothing'$ is the halting set. The source additionally asks whether an "analogous extension property" characterizes superlow c.e. degrees. It does not give that property or its quantifiers, so a precise equivalence cannot be supplied. Directly replacing $D$ by a c.e. degree in the displayed formula would make it impossible: a c.e. representative $W$ of $D$ would force $D\leq_T\deg_T(A)$. The intended analogy therefore requires clarification.

Short English statement

The record asks for all Weihrauch comparisons among five named problems, two implications relating Turing determinacy and dependent choice, and an extension property for properly $2$-c.e. degrees together with a proposed characterization of superlow c.e. degrees. Missing problem representations, the definition of strong Turing determinacy, the background set theory, and the unspecified analogous extension property prevent a completely precise formulation. The supplied partially solved label is dated curation, not an independently verified conclusion.

Sources

• Local UnsolvedMath registry, supplied complete record: permanent ID $30004680$, title "Weihrauch Determinacy and Degree Structure Questions," exact source problem code catalogue entry, collection "Oberwolfach Reports Open Problems." The record gives proposed year $2021$ and names no individual proposer.
• 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 supplied background describes these reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source: "Oberwolfach Report 21/2021." https://ems.press/content/serial-article-files/46899.
• Supplied literature source: Arslanov and Yamaleev, "definability in the difference hierarchy." https://doi.org/10.1134/S1995080218050037.
• Supplied literature source: Goh, Pauly and Valenti, "weakness of DS." https://arxiv.org/abs/2401.11807.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the bundle "partially solved" and says that the full questions are not jointly settled, while the report records partial results and solved easier cases. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment; time-sensitive status and cited claims require independent checking.