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.

Let A and B be subsets of the set of natural numbers. The well-known strong reducibilities are dened as follows: A m B i 2 B)) A 1 B i A m B and the reduction function f is one-one. where T ot denotes the set of total recursive functions. These reducibilities induce an equivalence relation of interreducibility, the equivalence classes of which are commonly called the m-degrees and the 1-degrees, respectively. The ordering of these degrees has been extensively studied. (...) In this paper the renements of the ordering of the m-degrees are studied by posing complexity conditions on the reduction func- tion. The discussion uses the axiomatic complexity theory and is hence very general. The paper is self-contained in the sense that the basic framework of the axiomatic complexity theory is brie y presented. (shrink)