Muchnik degrees and cardinal characteristics

Abstract

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/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{IOE}(2^{2^n})$. As a dual of the problem $\mathcal{D}(p)$, define $\mathcal{B}(p)$, for $0\le p<1/2$, to be the set of bit sequences $y$ such that $\underline{\rho }(x\leftrightarrow y)>p$ for each computable set~$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/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{IOE}$: We study cardinal characteristics in the sense of set theory that are analogous to the highness properties above.

Updated April 2020, to appear in J. Symb. Logic

References in corpus (2)

• Kolmogorov complexity and the Recursion Theorem
• Muchnik degrees and cardinal characteristics

Cited by in corpus (1)

• Muchnik degrees and cardinal characteristics