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...