patternModerate
Can one show NP-hardness by Turing reductions?
Viewed 0 times
showcanhardnessonereductionsturing
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#11120, answer score: 19
Revisions (0)
No revisions yet.