# Open problems on measures of relative randomness

In my article
*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*,
I compiled a number of open questions on the topic of "measures of relative randomness".
I also discussed this area in terms of the progress that has been achieved in the last ten years, and
the challenges that remain to be solved.

Here is a selection from these open problems, along with relevant facts.

For definitions of the measures of complexity that are discussed, please refer to the above article of mine.

From

*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.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. For these results, see my survey*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.From

*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.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. For these results, see my survey*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.From

*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.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*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.-
From

*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.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*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*. -
From

*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.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_n | A_n) \leq c$, where $W_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. For these results, see my survey*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*. -
From

*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.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_n), K(Y_n)\} \leq K(n) + c$, where $X_n$ is the $n$-bit prefix of $X$? 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. For these results, see my survey*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*. -
From

*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.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. For these results, see my survey*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*. -
From

*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.This question asks for which oracles $A$ the class $\{X | X \leq_{K} A\}$ or the class $\{X | X \leq_{C} A\}$ is uncountable. We know that given a set $A$, the class $\{X | X \leq_{LK} A\}$ is countable if and only if $\liminf (K(n)-K^Y(n))<\infty$. Moreover, a c.e. set $A$ is $K$-trivial if and only if $\{X | X \leq_{LK} A\}$ is uniformly computable from 0'. A $\Delta^0_2$ set $A$ is $K$-trivial iff $\{X | X \leq_{LK} A\}$ is countable. For these results, see my survey*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*. I conjecture that A real has countable $\leq_C$-lower cone if and only if it is infinitely often C-trivial. Moreover I conjecture that A real has countable $\leq_K$-lower cone if and only if it is infinitely often K-trivial. -
From

*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.Here $Y_n$ is the $n$-bit prefix of $Y$ (and similarly for $X$). We know that if $X$ is 1-random then $K(X_n)-n$ grows fast, in the sense that the sum of all $2^{n-K(X_n)}$ is finite. For these results, see my survey*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*. -
From

*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.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. For these results, see my survey*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*. -
From

*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.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. For these results, see my survey*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*. -
From

*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.Here $\mathcal{K}_c$ is the class of sequences $X$ such that $K(X_n)\leq K(n)+c$ for all $n$ (where $X_n$ is the $n$-bit prefix of $X$). 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. For these results, see my survey*Algorithmic randomness and measures of complexity, Bulletin of Symb. Logic 19(3) 2013*.