Abstract

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.