The universality of polynomial time Turing equivalence
arXiv:1601.03343 · doi:10.1017/S0960129516000232
Abstract
We show that polynomial time Turing equivalence and a large class of other equivalence relations from computational complexity theory are universal countable Borel equivalence relations. We then discuss ultrafilters on the invariant Borel sets of these equivalence relations which are related to Martin's ultrafilter on the Turing degrees.
Minor corrections