Open Problems in Mathematical Logic — Problem 25

Definitions and mathematical statement

Write ${\mathbb{N}}=\{0,1,2,\ldots\}$ and $2{\mathbb{N}}=\{2m:m\in{\mathbb{N}}\}$. A set is computably enumerable (c.e.) if an algorithm enumerates its elements. For $A\subseteq{\mathbb{N}}$, let $A\upharpoonright n$ denote the length-$n$ initial segment of its characteristic sequence. Under the usual interpretation of the source notation, $C(\sigma\mid\tau)$ is the plain conditional Kolmogorov complexity of a finite binary string $\sigma$ given a finite binary string $\tau$, with respect to a fixed optimal machine.

The source asks whether the following assertions hold.

1. For every c.e. set $A\subseteq{\mathbb{N}}$, there exist a c.e. set $D\subseteq2{\mathbb{N}}$ and a constant $c\in{\mathbb{N}}$ such that \[ A\equiv_{rK}D \] and, for every $n\in{\mathbb{N}}$, \[ C(A\upharpoonright n\mid D\upharpoonright n)\leq c, \qquad C(D\upharpoonright n\mid A\upharpoonright n)\leq c. \] The constant may depend on $A$, $D$, and the fixed machine, but not on $n$. These inequalities express the two supplied $O(1)$ bounds.
2. The source asks whether every $x$ has a random $z$ satisfying $z\geq_{rK}x$, and gives $z\geq_Kx$ as a parenthetical alternative. Using $X$ for the intended universe and $\operatorname{Random}$ for the intended randomness predicate, the two candidate assertions are \[ \forall x\in X\;\exists z\in X\; \left(\operatorname{Random}(z)\land z\geq_{rK}x\right) \] and \[ \forall x\in X\;\exists z\in X\; \left(\operatorname{Random}(z)\land z\geq_Kx\right). \]

The supplied record does not define $\equiv_{rK}$, $\geq_{rK}$, or $\geq_K$. It also does not specify the universe or randomness notion in part (2). Thus $X$ and $\operatorname{Random}$ above are unresolved placeholders, not additional hypotheses attributed to the source. The parenthetical alternative is retained without deciding whether both versions are separate questions or whether either version would satisfy the intended request. These missing conventions prevent a fully specified mathematical formulation.

Short English statement

The first question asks whether every computably enumerable set has a computably enumerable representative supported on even numbers, equivalent under the source's $rK$ relation, whose equal-length initial segments have bounded plain conditional complexity in both directions. The second asks whether every object lies below a random object under $rK$, with $K$ offered as an alternative. The relations, domain, and randomness notion require clarification. The registry labels the problem open; this draft does not independently verify that status.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $801013$, exact source problem code catalogue entry, title Open Problems in Mathematical Logic --- Problem 25, in the AMR Open Problem Lists collection. The registry attributes the record to Barmpalias, Gao et al., with proposed year 2026, and supplies the status open.
• Supplied source-list attribution: Barmpalias, Gao et al., Open Problems in Mathematical Logic (2026), Problem 25, https://arxiv.org/abs/2608.26628. The record reports access on 2026-10-16 and extraction by arxiv_latex. These are supplied provenance statements; the source has not been independently visited or verified for this draft.
• Supplied upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82. The registry records its update at 2026-10-16T14:00:00Z. No separate primary reference or definitions of the reducibilities are supplied in the record.