2 citations · 3 across the 2 of their papers we have counts for
4 papers · 1 filter
A minimal set low for speed
Rod Downey, Matthew Harrison-Trainor
An oracle is low-for-speed if it is unable to speed up the computation of a set which is already computable: if a decidable language can be decided in time using as…
Relationships between computability-theoretic properties of problems
Rod Downey, Noam Greenberg, Matthew Harrison-Trainor +2
A problem is a multivalued function from a set of \emph{instances} to a set of \emph{solutions}. We consider only instances and solutions coded by sets of integers. A problem admit…
Solovay functions and their applications in algorithmic randomness
Laurent Bienvenu, Rod Downey, Wolfgang Merkle +1
Classical versions of Kolmogorov complexity are incomputable. Nevertheless, in 1975 Solovay showed that there are computable functions such that for infinitely many st…
On the Orbits of Computably Enumerable Sets
Peter Cholak, Rod Downey, Leo Harrington
The goal of this paper is to show there is a single orbit of the c.e. sets with inclusion, , such that the question of membership in this orbit is -complete. Th…