On Polynomial-Time Relation Reducibility
Su Gao and Caleb
Ziegler
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 non-trivial equivalence classes and those whose equivalence classes
are all finite.
Table of Contents
|
1. Introduction 2. Preliminaries 3. Structural results between Eλ and id 4. More benchmarks and
non-reducibility results 5. Finitary equivalence
relations 6. Open problems References Acknowledgments |