1
$\begingroup$

I got recently confused when I noticed that there exists 2 types of polytime reductions, which lead to 2 different concepts of NP-hardness.

This is well explained in the answer to this question: Can one show NP-hardness by Turing reductions?

While a Karp reduction is required to show whether a problem is NP-Hard or co-NP-Hard, with Cook (aka Turing) reductions one only shows that a problem is "Cook-NP-hard", in a sense which does not distinguish NP-hardness from co-NP-hardness. More precisely,

  • In a Karp reduction, you map each instance $I$ of Problem $A$ to an instance $f(I)$ of Problem $B$, where $f(I)$ can be computed in polytime, and such that $$I \text{ is a Yes-instance for $A$} \iff f(I) \text{ is a Yes-instance for $B$}.$$ If $A$ is (Karp-)NP-Hard, this shows that $B$ is (Karp)-NP-Hard, too. And if $A$ is (Karp-)co-NP-hard, this shows that $B$ is (Karp)-co-NP-Hard, too.

  • In a Cook-reduction, you assume that there exists a polytime procedure $F$ to solve Problem $B$, and you show that Problem $A$ could be solved by calling this procedure a polynomial number of times. If Problem $A$ is known to be NP-hard, this shows that $B$ is (cook)-NP hard, but this does not tell us anything about the membership of $B$ in (Karp)-NP-Hard or (Karp)-co-NP-Hard.

1) In my understanding, Karp reductions only apply to decision problems, while we can show that any kind of problem is Cook-NP-Hard, is that correct?

2) If I want to prove that a problem is NP-complete, is it enough to show that this problem is Cook-NP-hard, and then to show that this problem is in NP? Similarly is a problem is Cook-NP-hard and in co-NP, does it prove that this problem is co-NP-complete?

3) A perhaps equivalent formulation of this question is as follows: While there is a distinction between the notions of Cook- and Karp-NP-Hardness, is there a real distinction between the notions of Cook- and Karp-NP-Completeness?

$\endgroup$
1
$\begingroup$

NP-hardness is a property of decision problems. It doesn't matter whether you define it using Karp reductions or Cook reductions.

NP-hardness and NP-completeness are defined using Karp reductions. If you prove that a problem is Cook-NP-hard, then it doesn't imply that it is Karp-NP-hard. Indeed, coSAT (the collection of unsatisfiable CNFs) is Cook-NP-hard but probably not Karp-NP-hard. Under reasonable hardness assumptions, there are even problems in NP which are Cook-NP-hard but not Karp-NP-hard. See for example Mandal, Pavan, and Venugopalan, Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis.

$\endgroup$
  • $\begingroup$ Thanks. Yes I understand that, but it does not answer my question 2): "Cook-NP-hard does not imply Karp-NP-hard", but maybe "Cook-NP-hard AND NP implies Karp-NP-complete" ? For example, it seems reasonnable to me to say that "coSAT is Cook-NP-Hard, and coSAT is in co-NP, hence coSAT is co-NP-complete" ? $\endgroup$ – guigux Nov 18 '17 at 9:43
  • $\begingroup$ Seems reasonable, but not known to be true, and suspected to be false: web.cs.iastate.edu/~pavan/papers/Ttt.pdf. $\endgroup$ – Yuval Filmus Nov 18 '17 at 9:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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