Back to Search
Start Over
Measuring the complexity of reductions between equivalence relations.
- Source :
- Computability; 2019, Vol. 8 Issue 3/4, p265-280, 16p
- Publication Year :
- 2019
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- SCHAUDER bases
MATHEMATICAL equivalence
NATURAL numbers
Subjects
Details
- Language :
- English
- ISSN :
- 22113568
- Volume :
- 8
- Issue :
- 3/4
- Database :
- Complementary Index
- Journal :
- Computability
- Publication Type :
- Academic Journal
- Accession number :
- 138696428
- Full Text :
- https://doi.org/10.3233/COM-180100