# If a problem is Cook-NP hard, and this problem is in NP, does it prove that the problem is Karp-NP-complete?

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?