Complexity of equivalence relations and preorders from computability theory

DOI10.1017/JSL.2013.33MaRDI QIDQ2933680zbMATH OpenOpenAlexFDO

Authors Egor Ianovski, Keng Meng Ng, André Nies, Russell Miller

Publication date 5 December 2014

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

Full work available at URL https://arxiv.org/abs/1302.0580, http://hdl.handle.net/10220/25392

zbMATH Keywords

\(m\)-reducibilitycomputability theorycomputable reducibilityequivalence relationsrecursion theory

Mathematics Subject Classification ID

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

Abstract: We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relations $R,S$, a componentwise reducibility is defined by $RleSiffexf,forallx,y,[xRylraf(x)Sf(y)].$ Here $f$ is taken from a suitable class of effective functions. For us the relations will be on natural numbers, and $f$ must be computable. We show that there is a $P{i}_1$-complete equivalence relation, but no $Pik$-complete for $kge2$. We show that $Sigmak$ preorders arising naturally in the above-mentioned areas are $Sigmak$-complete. This includes polynomial time $m$-reducibility on exponential time sets, which is $Sigma2$, almost inclusion on r.e. sets, which is $Sigma3$, and Turing reducibility on r.e. sets, which is $Sigma4$.

Recommendations

• \(\Sigma^ n_ 0\)-equivalence relations
• Equivalence relations that are ^0_3 complete for computable reducibility (extended abstract)
• Weakly precomplete equivalence relations in the Ershov hierarchy
• Finitary reducibility on equivalence relations
• The complexity of index sets of classes of computably enumerable equivalence relations

Cites work

• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• Strong isomorphism reductions in complexity theory
• Universal recursion theoretic properties of r.e. preordered structures

Cited in

(21)

• Positive preorders
• Subrecursive equivalence relations and (non-)closure under lattice operations
• Index sets for classes of positive preorders
• Minimal equivalence relations in hyperarithmetical and analytical hierarchies
• Universality for left-computably enumerable metric spaces
• On the degree structure of equivalence relations under computable reducibility
• Weakly precomplete equivalence relations in the Ershov hierarchy
• On polynomial-time relation reducibility
• Equivalence relations that are ^0_3 complete for computable reducibility (extended abstract)
• Finitary reducibility on equivalence relations
• EFFECTIVE INSEPARABILITY, LATTICES, AND PREORDERING RELATIONS
• Primitive recursive equivalence relations and their primitive recursive complexity
• The big-O problem
• Measuring the complexity of reductions between equivalence relations
• Computable embeddability for algebraic structures
• Logical Approaches to Computational Barriers
• ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS
• COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR
• On diagonal functions for equivalence relations
• Countable and finitary reductions on equivalence relations
• Analogues of the countable Borel equivalence relations in the setting of computable reducibility

This page was built for publication: Complexity of equivalence relations and preorders from computability theory

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