<p>No, no such <em>natural</em> problem is known. The reason is that, as far as I know, <a href="https://cstheory.stackexchange.com/a/21274/129">all natural $\mathsf{NP}$-complete problems are known to be p-isomorphic to SAT</a>, and the Cook-Levin Theorem in fact shows that SAT is complete for $\mathsf{NP}$ under one-one reductions. Combining the one-one reduction to SAT with a p-isomorphism gives a one-one reduction to any p-isomorphic problem.</p>

<p>In fact, even the potential "unnatural" counterexamples to the Isomorphism Conjecture - the k-creative sets of <a href="http://dx.doi.org/10.1016/0304-3975(85)90140-9" rel="nofollow noreferrer">Joseph and Young</a>'s Theorem 2.2 - are complete under one-one reductions by construction.</p>

<p>[Repeated from my comment <a href="https://cstheory.stackexchange.com/a/172/129">here</a>:] Since most many-one reductions we build are in fact one-one reductions, why don't we study those when they are formally stronger and we get them most of the time anyways? I think because it's simpler not to have to bother proving injectivity, even though we usually have it. In that sense, maybe many-one reductions are sort of the "Goldilocks reductions:" just the right power, just the right simplicity of proof.</p>

CC BY-SA 3.0
2015-08-27T17:46:22.590Z
Is there an intuitive explanation of set creativity?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-30T09:07:38.017Z
Thank you for you answer. I wish I was able to accept two answers.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-27T15:12:44.553Z
2015-08-27T15:12:44.553Z
2017-04-13T12:32:28.080Z
Joshua Grochow
<p>Actually, injective reductions are useful in cryptography. 
Suppose you have a ZK proof system for an NP relation R over the language L. 
If you want to build a ZK proof for another NP relation R' over a language L', you have to find two functions f and g with the following properties:
1. x belongs to L' iff f(x) belongs to L,
2. If (x,w) belongs to R' then (f(x),g(x,w)) belongs to R.
3. Moreover, f and g have to be efficiently computable.</p>

<p>The above properties imply that if the proof system for R is complete and sound, the proof system for R' (defined in the obvious way using the above functions to reduce instances of a relation to the other one) is complete and soundness as well.</p>

<p>What about proving that the new system is also ZK or witness-indistinguishable (WI)?
If f is invertible you can prove that the so obtained proof system is ZK.
Otherwise, to prove that you have to assume that the proof system for R is auxiliary-input ZK (rather than just ZK).
For WI, if f is invertible you can prove that the proof system for R' is WI. Without the fact that f is invertible, I am not sure if you can prove that</p>

CC BY-SA 4.0
2019-09-07T08:34:31.213Z
2019-09-07T08:40:51.480Z
2019-09-07T08:40:51.480Z
Vincenzo IOVINO
<p>Here is an answer to a special case, when we restrict ourselves to the case when the Karp reduction can also be made <strong>length-increasing</strong>, along with making it injective.  (Length-increasing means that $|f(x)|&gt;|x|$, where $f$ is the function that represents the reduction.) </p>

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

<p><strong>Proof.</strong>
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:</p>

<ol>
<li><p>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$.</p></li>
<li><p>There is at least one among these functions, for which the inverse is <strong>not</strong> 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.)</p></li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2015-08-26T10:40:30.317Z
The inverse of a length-increasing function is length-*decreasing*. Or am I missing something?
Emil Jeřábek
CC BY-SA 3.0
2015-08-26T10:46:41.270Z
Also, does p-isomorphism of NP-complete problems imply P != NP for the trivial reason that a one-element language is not isomorphic to a two-element language, or is it more sophisticated? If you allow finite languages, the claim has a simple direct proof, and only needs injectivity: namely, a one-element language is NP-complete under many-one reductions if P = NP, but can't be NP-complete under one-one reductions.
Emil Jeřábek
CC BY-SA 3.0
2015-08-26T13:07:44.827Z
@EmilJeřábek So, we know that if P=NP then every non-trivial language (other than $\phi$ and $\sigma^*$) is NP-complete under Karp reduction but not under injective Karp reduction. Therefore, every finite set is not NP-complete under injective Karp reduction since SAT is dense. So, Why do we insist on many-one polynomial reductions if every Karp reduction can be made injective (to natural problems)?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-26T13:59:37.753Z
Why should we insist on injective reductions instead? Injectivity does not seem to be in any way connected to the purpose of reductions, so the natural choice is not to demand it. There are many other arbitrary restrictions one might impose, but what would be the point?
Emil Jeřábek
CC BY-SA 3.0
2015-08-26T14:25:07.690Z
@EmilJeřábek If we adopt injective reductions we prevent silly sets from being NP-complete such as one-element sets and finite sets (those are always in P).
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-26T16:00:07.573Z
Why shouldn’t finite sets be NP-complete when P = NP? Note that in this situation, other silly sets are NP-complete even under one-one reductions, such as the set of all odd binary numbers.
Emil Jeřábek
CC BY-SA 3.0
2015-08-27T15:35:50.723Z
@EmilJeřábek: Even if one does not allow finite sets, there is still the fact that SAT is not sparse, sparsity is preserved by p-isomorphism, and P contains sparse (and simultaneously infinite) sets. But yes, under the usual definitions, finite sets work just fine.
Joshua Grochow
CC BY-SA 3.0
2015-08-30T19:55:21.137Z
It seems to me there is another potential problem, besides that raised by Emil in the first comment. Namely, the inverse of n one-one reduction $f$ is only *defined* on the image of $f$, not everywhere (unless $f$ happened to be surjective as well), so the inverse of $f$ is not a reduction, and therefore doesn't satisfy the hypothesis of the result used in point 1.
Joshua Grochow
CC BY-SA 3.0
2015-08-31T20:35:00.633Z
@JoshuaGrochow You are right, I indeed forgot to mention that we need a little more than injectivity, although less than surjectivity (so the inverse does not have to be a reduction). What is needed is that the inverse image can be computed in p-time, or else the algorithm tells, also in p-time,  that there is no inverse image. The referred theorem in point 1 applies to this case. That is, the reduction $f$  does not have to be surjective, but for a given $y$ we either should be able to find an $x$ with $f(x)=y$, or tell that no such $x$ exists, and all this in polynomial time.
Andras Farago
CC BY-SA 3.0
2015-09-01T01:10:29.307Z
@AndrasFarago: I understand that that's the relevant notion of "poly-time invertible." My point was that the inverse of f doesn't automatically give you an inv,li-reduction in the opposite direction, but the theorem you cite needs inv,li-reductions in *both* directions.
Joshua Grochow
CC BY-SA 3.0
2015-09-01T16:48:19.580Z
@JoshuaGrochow We do not need to obtain an inv,li reduction from the inverse to take care of the opposite durection. If we take two NP-complete languages, they both have a Karp reduction to the other (but these reductions are generally not the inverse of each other). If now we assume that _any_ Karp reduction can be made inv,li, then we obtain an inv,li reduction in _both_ directions, so by the cited theorem they can be transformed into a p-isomorphism.
Andras Farago
CC BY-SA 3.0
2015-09-02T05:36:03.107Z
Ah, I see - I missed that you were only applying this to reductions between two problems *both* of which were NP-complete. Excellent!
Joshua Grochow
CC BY-SA 3.0
2015-08-25T20:51:20.790Z
2015-08-26T15:08:37.280Z
2015-08-26T15:08:37.280Z
Andras Farago
<p>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).</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>One obvious gain is that sparse sets can not be complete under injective Karp reductions.</p>

CC BY-SA 3.0
2015-08-25T19:13:11.077Z
Why did Karp use many-one polynomial time reductions instead of one-one reductions? Was he influenced by reductions used in computability theory?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-27T06:14:26.267Z
I think I already kind of addressed this (or a very closely related) question in a comment on this response: http://cstheory.stackexchange.com/a/172/129.
Joshua Grochow
CC BY-SA 3.0
2015-08-27T07:03:04.100Z
@JoshuaGrochow Injectivity gives us lower bound on the density of hard sets. Are you aware of any NP-complete problem not known to be complete under injective Karp reductions? Please consider posting your comment as an answer.
Mohammad Al-Turkistany
<cc.complexity-theory>
Completeness under injective Karp reductions
Mohammad Al-Turkistany
# Completeness under injective Karp reductions

(Asked by: username_0 on 2015-08-25)

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.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_0**: Why did Karp use many-one polynomial time reductions instead of one-one reductions? Was he influenced by reductions used in computability theory?  
> **username_1**: I think I already kind of addressed this (or a very closely related) question in a comment on this response: http://cstheory.stackexchange.com/a/172/129.  
> **username_0**: @JoshuaGrochow Injectivity gives us lower bound on the density of hard sets. Are you aware of any NP-complete problem not known to be complete under injective Karp reductions? Please consider posting your comment as an answer.  

---

## 3 answers

### Answer by username_3 on 2015-08-25. Score: 8 | Accepted answer

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)|>|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:

1. 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$.
2. 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.

> **Comments:**
> **username_4**: The inverse of a length-increasing function is length-*decreasing*. Or am I missing something?  
> **username_4**: Also, does p-isomorphism of NP-complete problems imply P != NP for the trivial reason that a one-element language is not isomorphic to a two-element language, or is it more sophisticated? If you allow finite languages, the claim has a simple direct proof, and only needs injectivity: namely, a one-element language is NP-complete under many-one reductions if P = NP, but can't be NP-complete under one-one reductions.  
> **username_0**: @EmilJeřábek So, we know that if P=NP then every non-trivial language (other than $\phi$ and $\sigma^*$) is NP-complete under Karp reduction but not under injective Karp reduction. Therefore, every finite set is not NP-complete under injective Karp reduction since SAT is dense. So, Why do we insist on many-one polynomial reductions if every Karp reduction can be made injective (to natural problems)?  
> **username_4**: Why should we insist on injective reductions instead? Injectivity does not seem to be in any way connected to the purpose of reductions, so the natural choice is not to demand it. There are many other arbitrary restrictions one might impose, but what would be the point?  
> **username_0**: @EmilJeřábek If we adopt injective reductions we prevent silly sets from being NP-complete such as one-element sets and finite sets (those are always in P).  
> **username_4**: Why shouldn’t finite sets be NP-complete when P = NP? Note that in this situation, other silly sets are NP-complete even under one-one reductions, such as the set of all odd binary numbers.  
> **username_1**: @EmilJeřábek: Even if one does not allow finite sets, there is still the fact that SAT is not sparse, sparsity is preserved by p-isomorphism, and P contains sparse (and simultaneously infinite) sets. But yes, under the usual definitions, finite sets work just fine.  
> **username_1**: It seems to me there is another potential problem, besides that raised by Emil in the first comment. Namely, the inverse of n one-one reduction $f$ is only *defined* on the image of $f$, not everywhere (unless $f$ happened to be surjective as well), so the inverse of $f$ is not a reduction, and therefore doesn't satisfy the hypothesis of the result used in point 1.  
> **username_3**: @JoshuaGrochow You are right, I indeed forgot to mention that we need a little more than injectivity, although less than surjectivity (so the inverse does not have to be a reduction). What is needed is that the inverse image can be computed in p-time, or else the algorithm tells, also in p-time,  that there is no inverse image. The referred theorem in point 1 applies to this case. That is, the reduction $f$  does not have to be surjective, but for a given $y$ we either should be able to find an $x$ with $f(x)=y$, or tell that no such $x$ exists, and all this in polynomial time.  
> **username_1**: @AndrasFarago: I understand that that's the relevant notion of "poly-time invertible." My point was that the inverse of f doesn't automatically give you an inv,li-reduction in the opposite direction, but the theorem you cite needs inv,li-reductions in *both* directions.  
> **username_3**: @JoshuaGrochow We do not need to obtain an inv,li reduction from the inverse to take care of the opposite durection. If we take two NP-complete languages, they both have a Karp reduction to the other (but these reductions are generally not the inverse of each other). If now we assume that _any_ Karp reduction can be made inv,li, then we obtain an inv,li reduction in _both_ directions, so by the cited theorem they can be transformed into a p-isomorphism.  
> **username_1**: Ah, I see - I missed that you were only applying this to reductions between two problems *both* of which were NP-complete. Excellent!  

---

### Answer by username_1 on 2015-08-27. Score: 8

No, no such *natural* problem is known. The reason is that, as far as I know, [all natural $\mathsf{NP}$-complete problems are known to be p-isomorphic to SAT](https://cstheory.stackexchange.com/a/21274/129), and the Cook-Levin Theorem in fact shows that SAT is complete for $\mathsf{NP}$ under one-one reductions. Combining the one-one reduction to SAT with a p-isomorphism gives a one-one reduction to any p-isomorphic problem.

In fact, even the potential "unnatural" counterexamples to the Isomorphism Conjecture - the k-creative sets of [Joseph and Young](http://dx.doi.org/10.1016/0304-3975(85)90140-9)'s Theorem 2.2 - are complete under one-one reductions by construction.

[Repeated from my comment [here](https://cstheory.stackexchange.com/a/172/129):] Since most many-one reductions we build are in fact one-one reductions, why don't we study those when they are formally stronger and we get them most of the time anyways? I think because it's simpler not to have to bother proving injectivity, even though we usually have it. In that sense, maybe many-one reductions are sort of the "Goldilocks reductions:" just the right power, just the right simplicity of proof.

> **Comments:**
> **username_0**: Is there an intuitive explanation of set creativity?  
> **username_0**: Thank you for you answer. I wish I was able to accept two answers.  

---

### Answer by username_2 on 2019-09-07. Score: 1

Actually, injective reductions are useful in cryptography.
Suppose you have a ZK proof system for an NP relation R over the language L.
If you want to build a ZK proof for another NP relation R' over a language L', you have to find two functions f and g with the following properties:
1. x belongs to L' iff f(x) belongs to L,
2. If (x,w) belongs to R' then (f(x),g(x,w)) belongs to R.
3. Moreover, f and g have to be efficiently computable.

The above properties imply that if the proof system for R is complete and sound, the proof system for R' (defined in the obvious way using the above functions to reduce instances of a relation to the other one) is complete and soundness as well.

What about proving that the new system is also ZK or witness-indistinguishable (WI)?
If f is invertible you can prove that the so obtained proof system is ZK.
Otherwise, to prove that you have to assume that the proof system for R is auxiliary-input ZK (rather than just ZK).
For WI, if f is invertible you can prove that the proof system for R' is WI. Without the fact that f is invertible, I am not sure if you can prove that


---

