Complexity of equivalence relations and preorders from computability theory

Journal of Symbolic Logic 79 (3):859-881 (2014)
  Copy   BIBTEX

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 byR≤S⇔ ∃f∀x, y[x R y↔fS f].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$.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 99,462

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2016-06-30

Downloads
33 (#563,778)

6 months
7 (#541,487)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Anti‐Mitotic Recursively Enumerable Sets.Klaus Ambos-Spies - 1985 - Mathematical Logic Quarterly 31 (29-30):461-477.

Add more references