Notre Dame Journal of Formal Logic 58 (2):271-285 (2017)

Abstract
We study the notion of polynomial-time relation reducibility among computable equivalence relations. We identify some benchmark equivalence relations and show that the reducibility hierarchy has a rich structure. Specifically, we embed the partial order of all polynomial-time computable sets into the polynomial-time relation reducibility hierarchy between two benchmark equivalence relations Eλ and id. In addition, we consider equivalence relations with finitely many nontrivial equivalence classes and those whose equivalence classes are all finite.
Keywords finitary equivalence relations   finite equivalence relations   strong reduction function  polynomial-time relation reducibility
Categories (categorize this paper)
DOI 10.1215/00294527-3867118
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,464
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Classifying Positive Equivalence Relations.Claudio Bernardi & Andrea Sorbi - 1983 - Journal of Symbolic Logic 48 (3):529-538.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
Analytic Equivalence Relations and Bi-Embeddability.Sy-David Friedman & Luca Motto Ros - 2011 - Journal of Symbolic Logic 76 (1):243 - 266.
? 0 N -Equivalence Relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351-358.
$\sum_{0}^{N}$ -Equivalence Relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351 - 358.
Feasible Graphs with Standard Universe.Douglas Cenzer & Jeffrey B. Remmel - 1998 - Annals of Pure and Applied Logic 94 (1-3):21-35.
Borel Equivalence Relations Which Are Highly Unfree.Greg Hjorth - 2008 - Journal of Symbolic Logic 73 (4):1271-1277.
Superrigidity and Countable Borel Equivalence Relations.Simon Thomas - 2003 - Annals of Pure and Applied Logic 120 (1-3):237-262.
Thin Equivalence Relations and Effective Decompositions.Greg Hjorth - 1993 - Journal of Symbolic Logic 58 (4):1153-1164.

Analytics

Added to PP index
2017-03-03

Total views
4 ( #1,283,309 of 2,520,771 )

Recent downloads (6 months)
1 ( #405,623 of 2,520,771 )

How can I increase my downloads?

Downloads

My notes