Complexity of Maximal Chains in Computable Well-Partial-Orders

Definitions and mathematical statement

A partial order is a pair $P=(D,\leq_P)$, where $\leq_P$ is reflexive, antisymmetric, and transitive on $D$. It is a well partial order if every sequence $(x_n)_{n\in{\mathbb{N}}}$ in $D$ has indices $i<j$ with $x_i\leq_P x_j$. A conventional computable presentation has a decidable domain $D\subseteq{\mathbb{N}}$ and a decidable order relation. This presentation convention makes the terminology explicit; the supplied record does not specify its coding conventions.

A chain is a subset $C\subseteq D$ such that \[ \forall x,y\in C\; (x\leq_P y\ \lor\ y\leq_P x). \] Under the usual inclusion interpretation, a chain $C$ is maximal if \[ \forall B\subseteq D\;\left[(C\subseteq B\ \land\ B\text{ is a chain in }P)\Longrightarrow B=C\right]. \] Write $\mathcal M(P)$ for the collection of such chains.

Source question. For computable well partial orders $P$, determine the computational complexity required of a function selecting a maximal chain in $P$. Schematically, a uniform selector would satisfy \[ \forall p\;\left[p\text{ codes a computable well partial order }P_p \Longrightarrow F(p)\text{ represents some }C\in\mathcal M(P_p)\right]. \] This is a schematic rendering, not a uniquely specified computability problem: the supplied record does not define the input codes, the representation of the output chain, the complexity measure, or the required behavior on invalid inputs. It also does not specify whether the intended bounds concern one uniform selector for all presentations or the complexity of chains in each individual presentation. Here maximality has been defined by inclusion; whether the report intends this notion or a chain of greatest possible order type requires checking the precise source passage. A well partial order restricts to a well-order on every chain, so these are meaningful but distinct maximality requirements. No particular complexity bound or exact unresolved theorem is supplied.

Short English statement

The question asks how much computational power is needed to select a maximal chain from a computable well partial order. A precise complexity claim requires a choice of representations, complexity measure, uniformity requirement, and intended meaning of maximality. The supplied record labels the problem partially solved but does not state the established bounds or the exact remaining target.

Sources

• Local UnsolvedMath registry, permanent ID $30001983$, title: Complexity of Maximal Chains in Computable Well-Partial-Orders; source problem code: catalogue entry. Collection: Oberwolfach Reports Open Problems. The record gives proposed year 2012 and names no proposer.
• Computability Theory (2012), Oberwolfach Reports, DOI 10.4171/owr/2012/08, pp. 397--455. Supplied source URL and literature reference labelled "original Oberwolfach report": https://doi.org/10.4171/owr/2012/08. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. No exact page or individual contribution for this question is supplied.
• Supplied literature assessment, checked at 2026-08-21: status partially_solved. The assessment states that the report proves substantial upper and lower complexity results for maximal chains in computable well partial orders, while the extracted general optimal-complexity question is not fully settled by those results. This is supplied dated curation, not independently verified here; time-sensitive status and cited claims require independent verification.
• The registry supplies statement status corrected_verified and reports that the mathematical content was checked against the official report, with notation, context, and question form normalized without changing the source-level claim. This is a supplied verification claim, not an independent verification in this draft.