Abstract

This paper discusses refinements of the natural ordering of them-degrees (1-degrees) of strong recursive reducibility classes. Such refinements are obtained by posing complexity conditions on the reduction function. The discussion uses the axiomatic complexity theory and is hence very general. As the main result it is proved that if the complexity measure is required to be linearly bounded (and space-like), then a natural class of refinements forms a lattice with respect to a natural ordering upon them.