Completeness under injective Karp reductions Karp reduction is polynomial time computable many-one reduction between two computational problems. Many Karp reductions are actually one-one functions. This raises the question whether every Karp reduction is injective (one-one function).


  Is there a natural $NP$-complete problem that is known to be complete only under many-one Karp reduction and not known to be complete under injective Karp reduction? What do we gain (and lose) if we define $NP$-completeness using injective Karp reduction?


One obvious gain is that sparse sets can not be complete under injective Karp reductions.
Here is an answer to a special case, when we restrict ourselves to the case when the Karp reduction can also be made length-increasing, along with making it injective.  (Length-increasing means that $|f(x)|&gt;|x|$, where $f$ is the function that represents the reduction.) 

Claim: If every Karp reduction in $NP$ can be transformed into one that is injective and  length-increasing, then $P\neq NP$ holds.

Proof.
Let us assume that every  Karp reduction in $NP$ can be transformed into one that is injective and length-increasing. Then there are two possibilities:


All these reductions are not just computable in polynomial time, but the inverse of each function, which exists after making the function injective, is also computable in polynomial time. It is known that if two languages are both reducible to each other  by reductions that are polytime computable, polytime invertible and length-increasing, then they are polytime isomorphic (see Theorem 7.4 in the book "Theory of Computational Complexity" by Ding-Zhu Du and Ker-I Ko). This would mean that all $NP$ complete languages are $p$-isomorphic, that is, the Isomorphism Conjecture holds, which is known to imply $P\neq NP$.
There is at least one among these functions, for which the inverse is not computable in polynomial time. This function would provide an example of a worst-case one-way function. It is known, however, that the existence of worst-case one-way functions also implies $P\neq NP$. (See Theorem 2.5 in the book "The Complexity Theory Companion" by Hemaspaandra and Ogihara.)


Therefore, the assumption that every  Karp reduction can be made injective and lenght-increasing implies $P\neq NP$, so it is likely very hard to prove. On the other hand, it might be easier to disprove because that does not seem to have such a dramatic consequence. It is also unclear, what happens if we drop the length-increasing assumption.