Complexity of equivalence relations and preorders from computability theory

• Main Authors: Ianovski, Egor, Miller, Russell, Ng, Keng Meng, Nies, Andre
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2015
• Subjects: DRNTU::Science::Mathematics::Mathematical logic
• Online Access: https://hdl.handle.net/10356/107263; http://hdl.handle.net/10220/25392
• Institution: Nanyang Technological University

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 .