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 defined by $ R\le S \iff \ex f \, \forall x, y \, [xRy \lra f(x) Sf(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 ${\Pi }_1$-complete equivalence relation, but no $\Pi k$-complete for $k\ge 2$. We show that $\Sigma k$ preorders arising naturally in the above-mentioned areas are $\Sigma k$-complete. This includes polynomial time $m$-reducibility on exponential time sets, which is $\Sigma 2$, almost inclusion on r.e.\ sets, which is $\Sigma 3$, and Turing reducibility on r.e.\ sets, which is $\Sigma 4$.

To appear in J. Symb. Logic

References in corpus (4)

• Computably Enumerable Equivalence Relations
• The hierarchy of equivalence relations on the natural numbers under computable reducibility
• Complexity Classes of Equivalence Problems Revisited
• Coding Methods in Computability Theory and Complexity Theory