Quasi-injective reductions (Q1314394): Difference between revisions

The paper is focused on quasi-injective reductions, i.e. reductions that map at most a finite number of domains elements to a given element in their range. First there are considered \(f(n) \widehat {-to} - 1\) reductions, i.e. finite-to-one reductions, and it is shown whether or not an \(f(n) \widehat {-to} - 1\) reducibility is more powerful than a \(g(n) \widehat {-to} - 1\) reducibility, namely \[ (\exists_ \infty n) \bigl[ f(n) > g(n) \bigr] \Leftrightarrow (\exists A,B) \Bigl[ A \leq^ p_{f(n) \widehat {-to} - 1} B \bigwedge A \nleq^ p_{g(n) \widehat {-to} - 1} B \Bigr] \] (the above result does not hold for \(f(n) - to - 1\) reductions). Second there are considered \(k - to - k'\) reductions, i.e. reductions for which no \(k'\) elements of the range are mapped to by more than \(k\) domain elements, and it is shown that a \(c - to - d\) reduction is more flexible than an \(a - to - b\) reduction exactly when the former has a larger base or, in the case of identical bases, when the former has a larger excess (the base and the excess of the reduction \(k - to - k'\) are defined to be \(\lfloor {k \over k'} \rfloor\) and respectively \(k - k' \lfloor {k \over k'} \rfloor)\).