Measuring the complexity of reductions between equivalence relations

DOI10.3233/COM-180100MaRDI QIDQ5211066zbMATH OpenOpenAlexWikidataFDO

Authors E. B. Fokina, Dino Rossegger, Luca San Mauro

Publication date 17 January 2020

Published in Computability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.10363

zbMATH Keywords

computable structure theorycomputably enumerable equivalence relationsequivalence relationsreducibilityreducibility degree spectra

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Other degrees and reducibilities in computability and recursion theory (03D30) Theory of numerations, effectively presented structures (03D45)

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.

Recommendations

• On the degree structure of equivalence relations under computable reducibility
• Equivalence of measures of complexity classes
• Equivalence of Measures of Complexity Classes
• Complexity classes of equivalence problems revisited
• The computational complexity of equivalence and isomorphism problems
• Complexity of equivalence relations and preorders from computability theory
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• Combinatorics of reductions between equivalence relations
• scientific article; zbMATH DE number 3950521
• Reducibilities among equivalence relations induced by recursively enumerable structures

Cited in

(7)

• Classifying equivalence relations in the Ershov hierarchy
• Automatic Evaluation of Reductions between NP-Complete Problems
• DEGREE SPECTRA OF ANALYTIC COMPLETE EQUIVALENCE RELATIONS
• Computing sets from all infinite subsets
• ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS
• Word problems and ceers
• COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR

This page was built for publication: Measuring the complexity of reductions between equivalence relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211066)