Can one show NP-hardness by Turing reductions?

In the paper Complexity of the Frobenius Problem by Ramírez-Alfonsín, a problem was proved to be NP-complete using Turing reductions. Is that possible? How exactly? I thought this was only possible by a polynomial time many one reduction. Are there any references about this?

Are there two different notions of NP-hardness, even NP-completeness? But then I am confused, because from a practical viewpoint, if I want to show that my problem is NP-hard, which do I use?

They started the description as follows:

A polynomial time Turing reduction from a problem $$P_1$$ to another problem $$P_2$$ is an algorithm A which solves $$P_1$$ by using a hypothetical subroutine A' for solving $$P_2$$ such that, if A' were a polynomial time algorithm for $$P_2$$ then A would be a polynomial time algorithm for $$P_1$$. We say that $$P_1$$ can be Turing reduced to $$P_2$$.

A problem $$P_1$$ is called (Turing) NP-hard if there is an NP-complete decision problem $$P_2$$ such that $$P_2$$ can be Turing reduced to $$P_1$$.

And then they use such a Turing reduction from an NP-complete problem to show NP-completeness of some other problem.

There are (at least) two different notions of NP-hardness. The usual notion, which uses Karp reductions, states that a language $$L$$ is NP-hard if every language in NP Karp-reduces to $$L$$. If we change Karp reductions to Cook reductions, we get a different notion. Every language which is Karp-NP-hard is also Cook-NP-hard, but the converse is probably false. Suppose that NP is different from coNP, and take your favorite NP-complete language $$L$$. Then the complement of $$L$$ is Cook-NP-hard but not Karp-NP-hard.

The reason that $$\overline{L}$$ is Cook-NP-hard is the following: take any language $$M$$ in NP. Since $$L$$ is NP-hard, there is a polytime function $$f$$ such that $$x \in M$$ iff $$f(x) \in L$$ iff $$f(x) \notin \overline{L}$$. A Cook reduction from $$M$$ to $$\overline{L}$$ takes $$x$$, computes $$f(x)$$, checks whether $$f(x) \in L$$, and outputs the converse.

The reason that $$\overline{L}$$ is not NP-hard (assuming NP is different from coNP) is the following. Suppose $$\overline{L}$$ were NP-hard. Then for every language $$M$$ in coNP, there is a polytime reduction $$f$$ such that $$x \in \overline{M}$$ iff $$f(x) \in \overline{L}$$, or in other words, $$x \in M$$ iff $$f(x) \in L$$. Since $$L$$ is in NP, this shows that $$M$$ is in NP, and so coNP$$\subseteq$$NP. This immediately implies that NP$$\subseteq$$coNP, and so NP=coNP.

If some Cook-NP-hard language $$L$$ is in P, then P=NP: for any language $$M$$ in NP, use the Cook reduction to $$L$$ to give a polytime algorithm for $$M$$. So in that sense, Cook-NP-complete languages are also "hardest in NP". On the other hand, it is easy to see that Cook-NP-hard=Cook-coNP-hard: a Cook reduction for $$L$$ can be converted to a Cook reduction for $$\overline{L}$$. So we lose some precision by using Cook reductions.

There are probably other shortcomings to using Cook reductions, but I'll leave that to other answerers.

• I have not yet completely understood all of this I must say. But I have another question, maybe you can answer this (since there are not so many other answers): what if I have a Turing red. from NP-complete problem A to some problem B and a Karp red. from problem B to probplem C. Does that establish NP-completeness of problem C (membership is no problem)? And in general, can I call the problem B NP-hard or rather (Turing) NP-hard? Thanks! Apr 10 '13 at 16:42
• Two Karp reductions compose to a Karp reduction, and two Cook reductions compose to a Cook reduction. Since a Karp reduction is also a Cook reduction, if you compose a Karp reduction and a Cook reduction then you get a Cook reduction. But in general you don't get a Karp reduction. Apr 10 '13 at 17:01
• @YuvalFilmus, could you please elaborate what you wanted to mean by $x \in M$ iff $f(x) \in L$ iff $f(x) \notin \overline{L}$? Sep 16 '16 at 20:36
• A Karp-reduction from $M$ to $L$ is a function $f$ (polytime in this case) such that $x \in M$ iff $f(x) \in L$. For every $f,x$ it always holds that $f(x) \in L$ iff $f(x) \notin \overline{L}$, where $\overline{L}$ is the complement of $L$ (with respect to the range of $f$). Sep 16 '16 at 21:21

That's fine. A polynomial-time Turing reduction is a Cook reduction (as in Cook-Levin theorem) and reducing an NP-complete problem to the new problem gives NP-hardness (as does a polynomial-tiem many-one reduction, AKA Karp reduction). Indeed, Karp reductions are just restricted Turing reductions anyway.

Where they differ (with regards to this question) is in showing membership. A Karp reduction from a problem to a problem in NP shows the first is in NP. A Cook reduction in the same direction doesn't.

• Thanks. I wasn't even aware that one shows membership by explicitely using a Karp reduction. But it makes sense. But one can show NP-membership by using a Turing reductions in both directions, right? Apr 8 '13 at 4:47
• @user2145167 no, Yuval's answer gives the full story here, but in short, Cook reductions are weaker, so allow more in - e.g. you can go from any co-NP problem via a Cook reduction to any NP-complete problem, which is not true for Karp reductions. Apr 8 '13 at 6:28