Complexity of equivalence relations and preorders from computability theory

• المؤلفون الرئيسيون: Ianovski, Egor, Miller, Russell, Ng, Keng Meng, Nies, Andre
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: English
• منشور في: 2015
• الموضوعات: DRNTU::Science::Mathematics::Mathematical logic
• الوصول للمادة أونلاين: https://hdl.handle.net/10356/107263; http://hdl.handle.net/10220/25392

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