Quasi-injective reductions
type: Item
instance of: scholarly article
title: Quasi-injective reductions
zbMATH Open document ID: 0811.68079
DOI: 10.1016/0304-3975(94)90137-6
published in: Theoretical Computer Science
publication date: 1994-02-22T00:00:00Z
review text: 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)\).
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 501201
zbMATH Keywords: quasi-injective reductions
author: Edith Hemaspaandra
author: Lane A. Hemaspaandra
reviewed by: Ferucio Laurenţiu Ţiplea
MaRDI profile type: Publication
Wikidata QID: Q114214845
full work available at URL: 0304-3975(94)90137-6
OpenAlex ID: W1964711880
cites work: P-Printable Sets
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Complexity Measures for Public-Key Cryptosystems
cites work: Q3862379
cites work: Q4040892
cites work: On hardness of one-way functions
description: scientific article; zbMATH DE number 501201