Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-14T10:55:14.771Z Has data issue: false hasContentIssue false
  • English
  • Français

The universality of polynomial time Turing equivalence

Published online by Cambridge University Press:  13 July 2016

ANDREW MARKS
ANDREW MARKS*
Affiliation:
University of California, Los Angeles, California, U.S.A. Email: marks@math.ucla.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

References

Ambos-Spies, K. and Nies, A. (1992). The theory of the polynomial many-one degrees of recursive sets is undecidable. In: STACS 92 (Cachan, 1992), Lecture Notes in Comput. Sci. 577 Springer, Berlin 209–218. MR1255600 (94m:03068)CrossRefGoogle Scholar
Baker, T., Gill, J. and Solovay, R. (1975). Relativizations of the ${\cal P} = ? {\cal N}{\cal P}$ question. SIAM Journal of Computational 4 (4) 431–442. {MR{0395311 (52 #16108).Google Scholar
Bennett, C.H. and Gill, J. (1981). Relative to a random oracle A, P A ≠ NP A ≠ co − NP A with probability 1. SIAM Journal of Computationa 10 (1) 96–113. MR605606 (83a:68044).Google Scholar
Blum, M. and Impagliazzo, R. (1987). Generic oracles and oracle classes (extended abstract). In: FOCS, 118–126.Google Scholar
Dougherty, R., Jackson, S. and Kechris, A.S. (1994). The structure of hyperfinite Borel equivalence relations. Transactions of the American Mathematical Society 341 (1) 193–225.Google Scholar
Downey, R. and Nies, A. (2000). Undecidability results for low complexity time classes. Journal of Computer and System Sciences 60 (2) part 2 465–479. Twelfth Annual IEEE Conference on Computational Complexity (Ulm, 1997). MR1785026 (2002d:03078).Google Scholar
Fortnow, L. (1994). The role of relativization in complexity theory. Bulletin of the European Association for Theoretical Computer Science 52 52–229.Google Scholar
Jackson, S., Kechris, A.S. and Louveau, A. (2002). Countable Borel equivalence relations. Journal of Mathematical Logic 2 (1) 1–80. MR1900547 (2003f:03066).Google Scholar
Kechris, A.S. (1999). New directions in descriptive set theory. Bulletin of Symbolic Logic 5 (2) 161–174. MR1791302 (2001h:03090).Google Scholar
Ladner, R.E. (1975). On the structure of polynomial time reducibility. Journal of the ACM 22 (1) 155–171.Google Scholar
Marks, A., Slaman, T.A. and Steel, J.R. (2016). Martin's conjecture, arithmetic equivalence, and countable borel equivalence relations. In: A.S., Löwe, B. and Steel, J.R. (eds.) Ordinal Definability and Recursion Theory: The Cabal Seminar, Volume III, Lecture Notes in Logic 43, Cambridge University Press, 200–219.Google Scholar
Martin, D.A. (1968). The axiom of determinateness and reduction principles in the analytical hierarchy. Bulletin of the American Mathematical Society 74 687–689. MR0227022 (37 #2607).Google Scholar
Martin, D.A. (1975). Borel determinacy. Annals of Mathematics 102 (2) 363–371. MR0403976 (53 #7785).Google Scholar
Rogers, H. Jr. (1967). Theory of Recursive Functions and Effective Computability, McGraw-Hill Book Co., New York. MR0224462 (37 #61).Google Scholar
Sacks, G.E. (1966). Degrees of Unsolvability, 2nd ed. Princeton University Press, Princeton, N.J. Google Scholar
Shinoda, J. and Slaman, T.A. (1990). On the theory of the PTIME degrees of the recursive sets. Journal of Computer and System Sciences 41 (3) 321–366. MR1079470 (92b:03049).Google Scholar
Shore, R.A. (1979). The homogeneity conjecture. Proceedings of the National Academy of Sciences U.S.A. 76 (9) 4218–4219. MR543312 (81a:03046).Google Scholar
Shore, R.A. (1982). On homogeneity and definability in the first-order theory of the Turing degrees. Journal of Symbolic Logic 47 (1) 8–16. MR644748 (84a:03046).Google Scholar
Thomas, S. (2009). Martin's conjecture and strong ergodicity. Archive for Mathematical Logic 48 (8) 749–759. MR2563815 (2011g:03120).CrossRefGoogle Scholar
Williams, J. and Thomas, S. (2016). The bi-embeddability relation for finitely generated groups II Archive for Mathematical Logic 55 (3) 385–396.Google Scholar