Separations by random oracles and ``almost'' classes for generalized reducibilities (Q2720330)

The authors say that a set \(D\) separates two binary relations \(\leq_r\) and \(\leq_s\) on the powerset \(2^{{\mathcal N}}\) of the natural numbers iff the lower cones of \(D\) with respect to \(\leq_r\) and \(\leq_s\) are different. Considering the the class of all oracles which separate the two given relations, the authors ask for the measure of \(D\) in \(2^{{\mathcal N}}\) under the uniform distribution on \(2^{{\mathcal N}}\) which is obtained by choosing elements of \(2^{{\mathcal N}}\) by independent tosses of a fair coin. The authors say that two binary relations on \(2^{{\mathcal N}}\) can be separated by random oracles iff the class of separating oracles has measure one. Let Almost\(_r\) be the class of sets for which the upper \(\leq_r\)-cone has measure \(1\). In this paper the authors obtain results about separations by random oracles and about Almost classes in the context of generalized reducibilities. The authors note that the concept of generalized reducibility comprises all natural resource-bounded reducibilities, but is more general. The results on generalized reducibilities yield corollaries about specific resource-bounded reducibilities.