12
$\begingroup$

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.

||cite|improve this question
$\endgroup$
  • $\begingroup$ Why did Karp use many-one polynomial time reductions instead of one-one reductions? Was he influenced by reductions used in computability theory? $\endgroup$ – Mohammad Al-Turkistany Aug 25 '15 at 19:13
  • 1
    $\begingroup$ I think I already kind of addressed this (or a very closely related) question in a comment on this response: cstheory.stackexchange.com/a/172/129. $\endgroup$ – Joshua Grochow Aug 27 '15 at 6:14
  • $\begingroup$ @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. $\endgroup$ – Mohammad Al-Turkistany Aug 27 '15 at 7:03
7
$\begingroup$

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.

||cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ The inverse of a length-increasing function is length-decreasing. Or am I missing something? $\endgroup$ – Emil Jeřábek Aug 26 '15 at 10:40
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Aug 26 '15 at 10:46
  • 1
    $\begingroup$ 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? $\endgroup$ – Emil Jeřábek Aug 26 '15 at 13:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Aug 26 '15 at 16:00
  • 2
    $\begingroup$ @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. $\endgroup$ – Andras Farago Sep 1 '15 at 16:48
7
$\begingroup$

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.

||cite|improve this answer
$\endgroup$
  • $\begingroup$ Is there an intuitive explanation of set creativity? $\endgroup$ – Mohammad Al-Turkistany Aug 27 '15 at 17:46
  • $\begingroup$ Thank you for you answer. I wish I was able to accept two answers. $\endgroup$ – Mohammad Al-Turkistany Aug 30 '15 at 9:07
1
$\begingroup$

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

||cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.