Lattice Embeddings for Abstract Bounded Reducibilities
Wolfgang Merkle · SIAM Journal on Computing · 2002
We give an abstract account of resource-bounded reducibilities as exemplified by the polynomially time- or logarithmically space-bounded reducibilities of Turing, truth-table, and many-one type. We introduce a small set of axioms that are satisfied for most of the specific resource-bounded reducibilities appearing in the literature. Some of the axioms are of a more algebraic nature, such as the requirement that the reducibility under consideration is a reflexive relation, while others are formulated in terms of recursion theory and, for example, are related to delayed computations of arbitrary recursive sets. The main technical result shown is that for any reducibility that satisfies these axioms, every countable distributive lattice can be embedded into any proper interval of the structure induced on the recursive sets. This extends a corresponding result for polynomially time-bounded reducibilities due to Ambos-Spies [Inform. and Control, 65 (1985), pp. 63--84], as well as a result on embeddings of partial orderings for axiomatically described reducibilities due to Mehlhorn [J. Comput. System Sci., 12 (1976), pp. 147--178].