Strong Medvedev reducibilities and the KL-randomness problem

Abstract

While it is not known whether each real that is Kolmogorov-Loveland random is Martin-Löf random, i.e., whether $\mathrm{KLR}\subseteq \mathrm{MLR}$, Kjos-Hanssen and Webb (2021) showed that $\mathrm{MLR}$ is truth-table Medvedev reducible (${\le }_{s,tt}$) to $\mathrm{KLR}$. They did this by studying a natural class Either(MLR) and showing that $\mathrm{MLR}{\le }_{s,tt}\mathrm{Either}(\mathrm{MLR})\supseteq \mathrm{KLR}$. We show that Degtev's stronger reducibilities (positive and linear) do not suffice for the reduction of MLR to Either(MLR), and some related results.