Polynomial clone reducibilities are generalizations of the truth-table reducibilities. A polynomial clone is a set of functions over a finite set X that is closed under composition and contains all the constant and projection functions. For a fixed polynomial clone ${\fancyscript{C}}$ , a sequence ${B\in X^{\omega}}$ is ${\fancyscript{C}}$ -reducible to ${A \in {X}^{\omega}}$ if there is an algorithm that computes B from A using only effectively selected functions from ${\fancyscript{C}}$ . We show that if A is Kurtz random and ${\fancyscript{C}_{1} (...) \nsubseteq \fancyscript{C}_{2}}$ are polynomial clones, then there is a B that is ${\fancyscript{C}_{1}}$ -reducible to A but not ${\fancyscript{C}_{2}}$ -reducible to A. This implies a generalization of a result first proved by Lachlan (Z Math Logik Grundlagen Math 11:17–44, 1965) for the case |X| = 2. We also show that the same result holds if Kurtz random is replaced by Kolmogorov–Loveland stochastic. (shrink)

LetA be any nonrecursive set. We define a hierarchy of sets (and a corresponding hierarchy of degrees) that are reducible toA based on bounding the number of queries toA that an oracle machine can make. WhenA is the halting problemK our hierarchy of sets interleaves with the difference hierarchy on the r.e. sets in a logarithmic way; this follows from a tradeoff between the number of parallel queries and the number of serial queries needed to compute a function with oracleK.