The universality of polynomial time Turing equivalence

摘要

We show that polynomial time Turing equivalence and a large class of other equivalencernrelations from computational complexity theory are universal countable Borel equivalencernrelations. We then discuss ultrafilters on the invariant Borel sets of these equivalencernrelations which are related to Martin’s ultrafilter on the Turing degrees.