Affiliations: [a] Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Austria. [email protected] | [b] Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Austria. [email protected] | [c] Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Austria. [email protected]
Abstract: Computable reducibility is a well-established notion that allows to compare the complexity of various equivalence relations over the natural numbers. We generalize computable reducibility by introducing degree spectra of reducibility and bi-reducibility. These spectra provide a natural way of measuring the complexity of reductions between equivalence relations. We prove that any upward closed collection of Turing degrees with a countable basis can be realised as a reducibility spectrum or as a bi-reducibility spectrum. We show also that there is a reducibility spectrum of computably enumerable equivalence relations with no countable basis and a reducibility spectrum of computably enumerable equivalence relations which is downward dense, thus has no basis.
