Affiliations: [a] Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Austria. ekaterina.fokina@tuwien.ac.at | [b] Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Austria. dino.rossegger@tuwien.ac.at | [c] Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Austria. luca.san.mauro@tuwien.ac.at
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.
