COMPLEXITY OF EQUIVALENCE RELATIONS AND PREORDERS FROM COMPUTABILITY THEORY
Egor Ianovski, Russell Miller, Keng Meng Ng, André Nies · Journal of Symbolic Logic · 2014
Abstract We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relationsR,S, a componentwise reducibility is defined by R≤S⇔ ∃f∀x, y[x R y↔f(x)S f(y)]. Here,fis taken from a suitable class of effective functions. For us the relations will be on natural numbers, andfmust be computable. We show that there is a ${\rm{\Pi }}_1^0$ -complete equivalence relation, but no ${\rm{\Pi }}_k^0$ -complete fork≥ 2. We show that ${\rm{\Sigma }}_k^0$ preorders arising naturally in the above-mentioned areas are ${\rm{\Sigma }}_k^0$ -complete. This includes polynomial timem-reducibility on exponential time sets, which is ${\rm{\Sigma }}_2^0$ , almost inclusion on r.e. sets, which is ${\rm{\Sigma }}_3^0$ , and Turing reducibility on r.e. sets, which is ${\rm{\Sigma }}_4^0$ .