Structural properties of bounded relations with an application to NP optimization problems

We introduce the notion bounded relation which comprises most resource boun ded reducibilities which can be found in the literature, including non-unif orm bounded reducibilities such as less than or equal to (P/poly)(T). We st ate conditions on bounded relations which are again satisfied for most boun ded reducibilities and which imply that every countable partial ordering ca n be embedded into every proper interval of the recursive degrees. As corol laries, we obtain that every countable partial ordering can be embedded int o every proper interval of (REC, less than or equal to (P/poly)(T)), as wel l as into every proper interval between either two maximization or two mini mization problems in the structures (NPO, less than or equal to (E)) and (N PO, less than or equal to (L)). For the two latter structures, we show furt her that the result about embeddings of partial orderings extends to embedd ings of arbitrary countable distributive lattices where in addition the lea st or the greatest element of the lattice can be preserved. Among other cor ollaries, we obtain that for both structures every non-trivial NP optimizat ion problem bounds a minimal pair. In connection with embeddings into NPO w e introduce a representation of maximization or minimization problems by po lynomial time computable functions. We consider decidability issues w.r.t. this representation and show for example that there is no effective procedu re which decides for a (subrecursive) index of a polynomial time computable function whether the corresponding maximization problem is approximable wi thin a constant factor. (C) 2001 Elsevier Science B.V. All rights reserved.