dc.contributor.authorIanovski, Egor
dc.contributor.authorMiller, Russell
dc.contributor.authorNg, Keng Meng
dc.contributor.authorNies, Andre
dc.identifier.citationIanovski, E., Miller, R., Ng, K. M.,& Nies, A. (2014). Complexity of equivalence relations and preorders from computability theory. The journal of symbolic logic, 79(03), 859-881.en_US
dc.description.abstractWe study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relations R; S, a componentwise reducibility is de ned by R ≤ S ⇔ ∃f ∀x, y [xRy ↔ f(x) S f(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 ∏ 0 1-complete equivalence relation, but no ∏ 0 k-complete for k≥2. We show that ∑ 0 k preorders arising naturally in the abovementioned areas are ∑ 0 k-complete. This includes polynomial time m-reducibility on exponential time sets, which is ∑ 0 2, almost inclusion on r.e. sets, which is ∑ 0 3, and Turing reducibility on r.e. sets, which is ∑ 0 4 .en_US
dc.format.extent25 p.en_US
dc.relation.ispartofseriesThe journal of symbolic logicen_US
dc.rights© 2014 Association for Symbolic Logic. This is the author created version of a work that has been peer reviewed and accepted for publication by The Journal of Symbolic Logic, Association for Symbolic Logic. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1017/jsl.2013.33].en_US
dc.subjectDRNTU::Science::Mathematics::Mathematical logic
dc.titleComplexity of equivalence relations and preorders from computability theoryen_US
dc.typeJournal Article
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen_US
dc.description.versionAccepted versionen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record