3
$\begingroup$

It is crucial to use the right notion of reduction to define completeness inside NP. Different notions of completeness inside NP may have significant impact on the properties of complete languages. Initially, P vs NP problem was formulated by Cook using polynomial-time Turing reductions. Later Karp refined the notion of completeness using polynomial-time many-one reductions. It is not known whether complete problems are equivalent under different notions of completeness ( Cook vs Karp reductions).

This post on CS Theory shows that defining completeness using injective Karp reductions would prove $P \ne NP$. The reason is that SAT is dense language and can not be reduced to a sparse language using injective Karp reductions. Mahaney's Theorem states that $P=NP$ if and only if there is a Karp reduction from SAT to a sparse language.

Also, one of the answers highlights the fact that all known Karp reductions to NP-complete problems are injective. There is no known natural NP-complete problem via Karp reduction that can not be made one-to-one. If Cook had defined NP-completeness using injective Karp reductions then the P vs NP problem could not existed.

What arguments do exist against defining completeness in NP using injective Karp reductions?

Proving the existence (or non-existence) of polynomial-time algorithms for SAT would be more satisfactory way to resolve P vs NP but it is important to link it to the existence (or non-existence) of incomplete languages inside NP. Ladner's theorem states the $P\ne NP$ if and only if there exists an incomplete language in $NP$ \ $P$ (under Karp reductions).

$\endgroup$
  • 3
    $\begingroup$ Isn't the title of this question a little misleading? The question that is really being asked is your second one: "What arguments do exist against defining completeness in NP using injective Karp reductions?" $\endgroup$ – Abel Oct 1 '16 at 2:36
  • 1
    $\begingroup$ @Abel edited the post to address your concern. $\endgroup$ – Mohammad Al-Turkistany Oct 1 '16 at 10:54
11
$\begingroup$

If, for some (mysterious) reason, injective reductions were taken as the standard, then, even if we couldn't reduce SAT to certain PTime problems by such restricted reductions, that wouldn't tell us that SAT can't be solved in PTime.

In other words, the fact that any PTime solvable problem can be reduced to any other (nontrivial) PTime solvable problem is no longer available if we impose strange restrictions, like injectivity, on the reductions. As a result, reducibility of SAT to other problems would no longer serve as a criterion for whether P=NP.

EDIT after discussion in comments: I think I now see your main error, namely the hypothesis, quoted from one of your comments, "if all Karp reductions between NP-complete problems are in fact injective." This hypothesis is false. For example, there is a Karp reduction of SAT to SAT that sends each instance $x$ to itself, except that, if $x$ is just a propositional variable, then its sends $x$ to the first propositional variable $v_1$. This is a many-one Karp reduction between NP-complete problems, but it is not injective.

One could consider a weaker and not obviously false hypothesis, namely that whenever there is a Karp reduction from one NP-complete problem X to another NP-complete problem Y then there also exists an injective Karp reduction from X to Y. This weaker hypothesis trivially implies P$\neq$NP, without any need for anything as complicated as sparse sets (and in fact without knowing about SAT).

Proof: Assume this weaker hypothesis, and assume, toward a contradiction, that P=NP. Then the PTime computable sets $\{0\}$ (where $0$ denotes the empty string) and its complement $C$ are both NP-complete, in the usual sense of many-one Karp reductions. In particular, each is many-to-one Karp reducible to the other (by a function taking only two distinct values). But there is no injective Karp reduction of $C$ to $\{0\}$; every Karp reduction must send all elements of $C$ to $0$ and would therefore be very far from injective.

$\endgroup$
  • 1
    $\begingroup$ Mahaney's Theorem states that $P=NP$ if and only if there is a Karp reduction from SAT to a sparse language. $\endgroup$ – Mohammad Al-Turkistany Oct 1 '16 at 0:09
  • 1
    $\begingroup$ @MohammadAl-Turkistany Does any of this work with injective Karp reductions? $\endgroup$ – Andreas Blass Oct 1 '16 at 1:39
  • 1
    $\begingroup$ I don't see how your latest comment is relevant to my answer. What, exactly, would you argue against Cook reductions? The crucial point is that $P\neq NP$ is equivalent to "there is no Karp reduction of SAT to your favorite nontrivial problem in P" and also equivalent to "there is no Cook reduction of SAT to your favorite nontrivial problem in P", but I see no reason to believe that it is also equivalent to "there is no injective Karp reduction of SAT to your favorite nontrivial problem in P." $\endgroup$ – Andreas Blass Oct 1 '16 at 15:42
  • 2
    $\begingroup$ Right. Cook reductions entered this thread only in your third comment. If you now claim they're irrelevant, then I agree. They are not mentioned in my answer. $\endgroup$ – Andreas Blass Oct 1 '16 at 17:53
  • 2
    $\begingroup$ My answer is about the same restricted version of Karp reduction, namely requiring the reducing function to be injective. You are, of course, free to consider it as unsatisfactory, since you apparently don't understand it. I assume that you are the person who downvoted it; I would hope that other readers can understand it. $\endgroup$ – Andreas Blass Oct 1 '16 at 18:02

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.