Muchnik degrees and cardinal characteristics

For $p\in [0,1]$ let $\mathcal{D}(p)$ be the mass problem of infinite bit sequences~$y$ (i.e., $\{0,1\}$-valued functions) such that for each computable bit sequence $x$, the bit sequence $x\leftrightarrow y$ has asymptotic lower density at most $p$ (where $x\leftrightarrow y$ has a $1$ in position $n$ iff $x(n)=y(n)$). We show that all members of this family of mass problems parameterized by a real $p$ with $0<p<1\mathrm{/}2$ have the same complexity in the sense of Muchnik reducibility. We prove this by showing Muchnik equivalence of the problems $\mathcal{D}(p)$ with the mass problem $\mathrm{I}\mathrm{O}\mathrm{E}(2^{2^n})$. As a dual of the problem $\mathcal{D}(p)$, define $\mathcal{B}(p)$, for $0 \le p < 1/2$,tobethesetofbitsequences$y$suchthat$\underline \rho (x \leftrightarrow y) > p$foreachcomputableset$x$. We prove that the Medvedev (and hence Muchnik) complexity of the mass problems $\mathcal{B}(p)$ is the same for all $p\in (0,1\mathrm{/}2)$, by showing that they are Medvedev equivalent to the mass problem of functions bounded by $2^{2^n}$ that are almost everywhere different from each computable function. Together with Joseph Miller, we obtain a proper hierarchy of the mass problems of type $\mathrm{I}\mathrm{O}\mathrm{E}$: We study cardinal characteristics in the sense of set theory that are analogous to the highness properties above.