3
$\begingroup$

My understanding is that when reducing one problem known to be NPC (e.g., HAM-Cycle) to another problem known to be NP (e.g., Ham-Path) we have shown that the second problem (the target of the reduction, or HAM-Path in the example) is NPC.

Now I also understand that this reduction must be many-one (or, equivalently, a Karp reduction.)

I came a across a reduction from Ham-Cycle to Ham-Path that called a decider for Ham-Path multiple times in the reduction algorithm. It seems that this would qualify as a Turing reduction and not a Karp reduction and so wouldn't qualify as a valid NPC reduction.

Reduction from Hamiltonian cycle to Hamiltonian path. I'm referring to the upvoted solution of Aryabhata (I don't have enough reputation to comment on his post.)

In general, I'm a little confused about the different kinds of reductions and which are valid for an NPC reduction (e.g., so clearly many-one and one-to-one reductions must both be valid for NPC proofs, right?)

Background: CLRS appears to define the reductions as mapping reductions and is the same as Sipser's book and because of the linked post this caused confusion. Upon further research on stack exchange, most things claim we need a many-one reduction, but were not sufficiently clear about what is going on.

$\endgroup$
  • $\begingroup$ NPC = NP complete $\endgroup$ – Carl Mummert Mar 24 '18 at 14:15
  • $\begingroup$ Your concern with the other answer is well founded; I left a comment there. Other answers to that question have genuine many-one reductions. $\endgroup$ – Carl Mummert Mar 24 '18 at 14:20
3
$\begingroup$

By what I think is the most common definition, a problem $R$ is NP complete if $R$ is in NP and every problem in NP is polynomial-time reducible to $R$ (that is, many-one reducible in polynomial time). If the reduction happens to be one-to-one that doesn't affect anything with this definition, it is just extra information.

This definition is specifically in terms of polynomial time many-one reductions, not polynomial time Turing reductions.

To see why, suppose that $R$ is a problem in P which is neither always true nor always false (so $R \not = \emptyset$ and $R \not = \mathbb{N}$) and suppose $E$ is the empty problem (always false, $E = \emptyset$). Then:

  • $R$ is polynomial-time Turing reducible to $E$: we can just ignore $E$ and use our polynomial time algorithm to determine whether a number is in $R$.

  • But $R$ is not polynomial-time many-one reducible to $E$: there is no function whatsoever so that $f(n) \in E$ if and only if $n \in R$.

So, in general, we cannot assume that polynomial time Turing reducibility (Cook reducibility) is equivalent to polynomial-time many-one reducibility (Karp reducibility).

Also, every problem is polynomial-time Turing reducible to its complement, but we don't want to claim that Co-NP-complete problems are NP-complete, or vice-versa. Focusing on many-one reductions rather than Turing reductions maintains the distinction between each problem and its complement.

[There is some small variation in the definitions. In his book Computational Complexity, Papadimitrou has a stricter definition of NP completeness, in which the reduction must be in L (logarithmic space) - thanks to Rob Arthan for pointing this out. The reduction is still a many-one reduction rather than a Turing reduction. Sipser's book Introduction to the Theory of Computation uses polynomial time reductions as above, and Hopcroft and Ullman also use this definition.]

$\endgroup$
  • 1
    $\begingroup$ Interestingly, in his well-known Computational Complexity, Papadimitriou defines NP-completeness using log-space reductions, although he does discuss the alternatives. I think you are right that the standard definition is via polynomial time reductions. $\endgroup$ – Rob Arthan Mar 24 '18 at 14:35

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.