21
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
20
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – user2145167
    Commented Apr 10, 2013 at 16:42
  • 5
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Commented Apr 10, 2013 at 17:01
  • $\begingroup$ @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}$? $\endgroup$
    – Omar Shehab
    Commented Sep 16, 2016 at 20:36
  • $\begingroup$ 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$). $\endgroup$
    – Yuval Filmus
    Commented Sep 16, 2016 at 21:21
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – user2145167
    Commented Apr 8, 2013 at 4:47
  • 2
    $\begingroup$ @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. $\endgroup$
    – Luke Mathieson
    Commented Apr 8, 2013 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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