• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Complexity of Equivalence Relations and Preorders from Computability Theory

Journal of Symbolic Logic. 2014. Vol. 3. No. 79. P. 859-881.
Ianovski E., Miller R. G., Ng K. M., Nies A.

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 ≤ S ⇔ ∃f ∀x, y [x R y ↔ 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  -complete equivalence relation, but no  -complete for k ≥ 2. We show that  preorders arising naturally in the above-mentioned areas are  -complete. This includes polynomial time m-reducibility on exponential time sets, which is  , almost inclusion on r.e. sets, which is  , and Turing reducibility on r.e. sets, which is  .