Please use this identifier to cite or link to this item:
Title: Complexity of equivalence relations and preorders from computability theory
Authors: Ianovski, Egor
Miller, Russell
Ng, Keng Meng
Nies, Andre
Keywords: DRNTU::Science::Mathematics::Mathematical logic
Issue Date: 2014
Source: Ianovski, 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.
Series/Report no.: The journal of symbolic logic
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 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 .
ISSN: 1943-5886
DOI: 10.1017/jsl.2013.33
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: [].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
461.4 kBAdobe PDFThumbnail

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.