COMPLEXITY OF EQUIVALENCE RELATIONS AND PREORDERS FROM COMPUTABILITY THEORY

DOI10.1017/jsl.2013.33zbMath1353.03043arXiv1302.0580OpenAlexW2170024339MaRDI QIDQ2933680

Keng Meng Ng, André Nies, Egor Ianovski, Russell G. Miller

Publication date: 5 December 2014

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

equivalence relationscomputability theoryrecursion theory\(m\)-reducibilitycomputable reducibility

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (10)

Primitive recursive equivalence relations and their primitive recursive complexity ⋮ ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS ⋮ Minimal equivalence relations in hyperarithmetical and analytical hierarchies ⋮ Universality for left-computably enumerable metric spaces ⋮ Unnamed Item ⋮ On the degree structure of equivalence relations under computable reducibility ⋮ Weakly precomplete equivalence relations in the Ershov hierarchy ⋮ EFFECTIVE INSEPARABILITY, LATTICES, AND PREORDERING RELATIONS ⋮ Computable embeddability for algebraic structures ⋮ Subrecursive equivalence relations and (non-)closure under lattice operations

Cites Work

• Strong isomorphism reductions in complexity theory
• Universal recursion theoretic properties of r.e. preordered structures
• Unnamed Item

This page was built for publication: COMPLEXITY OF EQUIVALENCE RELATIONS AND PREORDERS FROM COMPUTABILITY THEORY