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.