Problems on relative randomness

In my survey Algorithmic randomness and measures of complexity (2013) I compiled some open questions related to relative randomness.

Is the structure of the $rK$, $LK$ or the $K$-degrees of c.e. sets dense?

Density relies heavily on the existence of join in a degree structure. This seems to be the obstacle in proving density in these degree structures. Not much is known about the existence or non-existence of a join in these degree structures of c.e. sets. We note that Sacks splitting holds for $K$, $LK$, $rK$, $C$ while a weak version of density holds for $LK$. Moreover there is a $\Delta^0_2$ nonzero $K$-degree which does not bound any nonzero c.e. $K$-degree.

Is there a minimal $LK$-degree? Minimal $K$-degree?

We know that there are minimal $C$ and $rK$ degrees. Moreover there is a minimal pair of $LK$ degrees below the degree of the halting problem. Globally, almost all $LK$-degrees have the countable predecessor property and almost all pairs of $LK$-degrees have greatest lower bound zero.

Do all or some pairs of $LK$-degrees have a least upper bound?

We know that the $LK$-degrees of c.e. reals (or c.e. sets or $\Delta^0_2$ sets) have no minimal pairs. The usual join operation fails badly to function as supremum. For these results and similar ones, see my [survey](../articles/ksurvey.pdf).

Is the quotient upper semi-lattice of the c.e. degrees modulo the $K$-trivials dense?

The class of oracles that do not improve the compression of strings is equal to the class of oracles with trivial initial segment prefix-free complexity. This is another way to say that the $K$-trivial sets are exactly the low for $K$ sets. We also know that the quotient upper semi-lattice of the c.e. Turing degrees modulo the K-trivial degrees has no minimal pairs. I proved this with Rod Downey, as a consequence of my work on minimal pairs in the $K$-degrees of c.e. sets or c.e. reals. For these results and related references, see my [survey](../articles/ksurvey.pdf).

Is every sequence reducible to a 1-random with respect to $\leq_{rK}$ or $\leq_K$?

We know that there exists a c.e. set $A$ such that for every c.e. set $W$, there exists a constant $c$ such that for all $n$ we have $C(W\upharpoonright_n | A\upharpoonright_n) \leq c$, where $W\upharpoonright_n$ is the first $n$ bits of $W$ (and similarly for $A$). Also, there is a c.e. real which is not $\leq_{cl}$-bounded by 1-random c.e. reals. Similarly, there exists a $\Delta^0_2$ real which is not $cl$-bounded by any 1-random.

Can the minimum of the prefix complexities of two nontrivial sets be trivial?

The precise statement of this question is: is there a pair of sets $X$, $Y$ which are not $K$-trivial and a constant $c$ such that for all $n$ we have $$\min\{K(X\upharpoonright_n), K(Y\upharpoonright_n)\} \leq K(n) + c.$$ We note that there exists a nontrivial $\Delta^0_2$ set $X$ whose initial segment prefix-free complexity does not bound the initial segment prefix-free complexity of any nontrivial c.e. set. On the other hand, for all pairs $A_i$, $i < 2$ of c.e. sets (or c.e. reals) which are not not K-trivial and all constants $c$, there exists a length $n$ such that the complexity of each of the $n$-bit prefixes of the two sets is above $K(n)+c$. In this sense, left c.e. reals with nontrivial initial segment complexity have some sort of common information, or at least complexity.

Is there a pair of $\Delta^0_2$ sets which form a minimal pair in the $K$-degrees?

We know that the structures of $rK$, $K$ and $C$ degrees of c.e. sets have a greatest degree. The $K$-degrees of 1-random $\Delta^0_2$ reals have no maximal or minimal elements. There are minimal pairs of c.e. sets with respect to the Solovay, the $rK$ and the $C$ reducibilities. However there are no minimal pairs in the $K$-degrees of c.e. sets.

Which reals are more complex than uncountably many reals?

This question asks for which oracles $A$ the class $\{X | X \leq_{K} A\}$ or the class $\{X | X \leq_{C} A\}$ is uncountable.

Are there 1-random $X,Y$ such that $\liminf (K(Y\upharpoonright_n)-K(X\upharpoonright_n))$ is finite but $X\leq_K Y$?

We know that if $X$ is 1-random then $K(X\upharpoonright_n)-n$ grows fast, in the sense that $\sum_n 2^{n-K(X\upharpoonright_n)}<\infty$.

Is there a maximal $K$-degree? Is there a minimal $K$-degree?

In the $K$-degrees of 1-random reals there are no maximal or minimal elements. There is a minimal pair in the $K$-degrees. In the $K$-degrees there is a pair of degrees with no upper bound.

Is there a maximal $cl$-degree in the c.e. reals?

Barmpalias and Lewis have shown a formal version of the following, in terms of genericity or randomness: "If a typical sequence is computed efficiently by another sequence, then the two sequences have the same information". In formal terms, randoms and generics are quasi-maximal in the $cl$-degrees.

Does the function $c\mapsto |\mathcal{K}_c|$ compute $\mathbf{0}'$ or even $\mathbf{0}''$?

Here $\mathcal{K}_c$ is the class of sequences $X$ such that $K(X\upharpoonright_n)\leq K(n)+c$ for all $n$.

We know that this function is not computable from $\mathbf{0}'$. We also know that, rather surprisingly, this function is computable from $\mathbf{0}''$. This question asks how much can this function compute. Once we know its proper place in the hierarchy of arithmetical complexity, this is a natural question.