12

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.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • 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 Aug 25 '15 at 19:13
  • 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. – Joshua Grochow Aug 27 '15 at 06:14
  • @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 Aug 27 '15 at 07:03

3 Answers3

8

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.

Andras Farago
  • 11,396
  • 37
  • 70
  • 2
    The inverse of a length-increasing function is length-decreasing. Or am I missing something? – Emil Jeřábek Aug 26 '15 at 10:40
  • 1
    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 Aug 26 '15 at 10:46
  • @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 Aug 26 '15 at 13:07
  • 1
    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 Aug 26 '15 at 13:59
  • @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 Aug 26 '15 at 14:25
  • 1
    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 Aug 26 '15 at 16:00
  • 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. – Joshua Grochow Aug 27 '15 at 15:35
  • 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 Aug 30 '15 at 19:55
  • @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 Aug 31 '15 at 20:35
  • @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 Sep 01 '15 at 01:10
  • 2
    @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 Sep 01 '15 at 16:48
  • 1
    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 Sep 02 '15 at 05:36
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, 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's Theorem 2.2 - are complete under one-one reductions by construction.

[Repeated from my comment here:] 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.

Community
  • 1
Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
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

Vincenzo IOVINO
  • 11
  • 2