Complexity of equivalence relations and preorders from computability theory

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 .