A mass problem is a set of functions$\omega \to \omega $. For mass problems${\mathcal {C}}, {\mathcal {D}}$, one says that${\mathcal {C}}$is Muchnik reducible to${\mathcal {D}}$if each function in${\mathcal {C}}$is computed by a function in${\mathcal {D}}$. In this paper we study some highness properties of Turing oracles, which we view as mass problems. We compare them with respect to Muchnik reducibility and its uniform strengthening, Medvedev reducibility.For$p \in [0,1]$let${\mathcal {D}}(p)$be the mass problem of infinite bit sequencesy(i.e.,$\{0,1\}$-valued functions) such that for each (...) computable bit sequencex, the bit sequence$ x {\,\leftrightarrow\,} y$has asymptotic lower density at mostp(where$x {\,\leftrightarrow\,} y$has a$1$in positionniff$x(n) = y(n)$). We show that all members of this family of mass problems parameterized by a realpwith$0 p$for each computable setx. 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.Next, together with Joseph Miller, we obtain a proper hierarchy of the mass problems of type$\text {IOE}$: we show that for any order functiongthere exists a faster growing order function$h $such that$\text {IOE}(h)$is strictly above$\text {IOE}(g)$in the sense of Muchnik reducibility.We study cardinal characteristics in the sense of set theory that are analogous to the highness properties above. For instance,${\mathfrak {d}} (p)$is the least size of a setGof bit sequences such that for each bit sequencexthere is a bit sequenceyinGso that$\underline \rho (x {\,\leftrightarrow\,} y)>p$. We prove within ZFC all the coincidences of cardinal characteristics that are the analogs of the results above. (shrink)

The tower number ${\mathfrak t}$ and the ultrafilter number $\mathfrak {u}$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $\omega $ and the almost inclusion relation $\subseteq ^*$ between such subsets. We consider analogs of these cardinal characteristics in computability theory.We say that a sequence $(G_n)_{n \in {\mathbb N}}$ of computable sets is a tower if $G_0 = {\mathbb N}$, $G_{n+1} \subseteq ^* G_n$, and $G_n\smallsetminus G_{n+1}$ is infinite for each n. (...) A tower is maximal if there is no infinite computable set contained in all $G_n$. A tower ${\left \langle {G_n}\right \rangle }_{n\in \omega }$ is an ultrafilter base if for each computable R, there is n such that $G_n \subseteq ^* R$ or $G_n \subseteq ^* \overline R$ ; this property implies maximality of the tower. A sequence $(G_n)_{n \in {\mathbb N}}$ of sets can be encoded as the “columns” of a set $G\subseteq \mathbb N$. Our analogs of ${\mathfrak t}$ and ${\mathfrak u}$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones.We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $\Delta ^0_2$ -set does so.We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively. (shrink)