Exact Pairs for Abstract Bounded Reducibilities
Wolfgang Merkle · Mathematical logic quarterly · 1999
Abstract In an attempt to give a unified account of common properties of various resource bounded reducibilities, we introduce conditions on a binary relation ≤ r between subsets of the natural numbers, where ≤ r is meant as a resource bounded reducibility. The conditions are a formalization of basic features shared by most resource bounded reducibilities which can be found in the literature. As our main technical result, we show that these conditions imply a result about exact pairs which has been previously shown by Ambos‐Spies [2] in a setting of polynomial time bounds: given some recursively presentable ≤ r ‐ideal I and some recursive ≤ r ‐hard set B for I which is not contained in I , there is some recursive set C , where B and C are an exact pair for I , that is, I is equal to the intersection of the lower ≤ r ‐cones of B and C , where C is not in I . In particular, if the relation ≤ r is in addition transitive and there are least sets, then every recursive set which is not in the least degree is half of a minimal pair of recursive sets.