patternModerate
Why NP is not closed under Turing reduction
Viewed 0 times
whyclosedunderreductionturingnot
Problem
The notion of polynomial time Turing reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using another algorithm as a subroutine.
For example, by stating "$A$ is polynomial time Turing reduced to $B$", we indicate that we can solve the problem $A$ in a polynomial number of steps by making use of an algorithm which can solve the problem $B$.
Then if $B$ is in $\mathsf{NP}$, why not $A$?
For example, by stating "$A$ is polynomial time Turing reduced to $B$", we indicate that we can solve the problem $A$ in a polynomial number of steps by making use of an algorithm which can solve the problem $B$.
Then if $B$ is in $\mathsf{NP}$, why not $A$?
Solution
The reason that $A$ is not defined as in NP is that we use a finer notion for NP-completeness, which is mapping (Karp) reductions.
Intuitively, in a Karp reduction, we not only want the problem $A$ to be solvable using an oracle for $B$, but we also require that this oracle is only used once, and only as the very last operation.
Why this notion and not Turing reductions? First - it works well, and it provides a finer distinction in complexity classes (more on that in a bit). Second, it captures the intuition that if you could solve $B$, then given input for $A$ you can convert it to input for $B$, rather than just use $B$ in some complex and clever manner. So in a way, it makes "very little use" of $B$. This is all philosophical, of course.
In practice, the main benefit of Karp reduction is that it differentiates $coNP$ from $NP$. Indeed, you can show a Turing reduction from $SAT$ to $\overline{SAT}$ (just call the oracle and flip the answer). So you cannot have the notion of coNP-complete v.s. NP-complete if you use Turing reductions.
You can read the discussion here for a more elaborate answer.
Intuitively, in a Karp reduction, we not only want the problem $A$ to be solvable using an oracle for $B$, but we also require that this oracle is only used once, and only as the very last operation.
Why this notion and not Turing reductions? First - it works well, and it provides a finer distinction in complexity classes (more on that in a bit). Second, it captures the intuition that if you could solve $B$, then given input for $A$ you can convert it to input for $B$, rather than just use $B$ in some complex and clever manner. So in a way, it makes "very little use" of $B$. This is all philosophical, of course.
In practice, the main benefit of Karp reduction is that it differentiates $coNP$ from $NP$. Indeed, you can show a Turing reduction from $SAT$ to $\overline{SAT}$ (just call the oracle and flip the answer). So you cannot have the notion of coNP-complete v.s. NP-complete if you use Turing reductions.
You can read the discussion here for a more elaborate answer.
Context
StackExchange Computer Science Q#12541, answer score: 10
Revisions (0)
No revisions yet.