4
$\begingroup$

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$?

$\endgroup$

migrated from cstheory.stackexchange.com Jun 8 '13 at 19:38

This question came from our site for theoretical computer scientists and researchers in related fields.

10
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

An oracle question "$x\in L?$" always answers "$x\notin L?$" as well. So if we choose $A=\overline{B}$ and the closure property you propose holds, $\overline{B}\in \mathsf{NP}$ would follow. This holds for all $B\in\mathsf{NP}$ and thus $\mathsf{NP}=$ co-$\mathsf{NP}$.

On the other hand, if $\mathsf{NP}=$ co-$\mathsf{NP}$, the closure of $\mathsf{NP}$ under Cook reductions ($P^{\mathsf{NP}}$) would be equal to $\mathsf{NP}$: $P^{\mathsf{NP}}=\mathsf{NP}\cup\text{co-}\mathsf{NP}=\mathsf{NP}$.

So your question is equivalent to: "Why is $\mathsf{NP}\neq\text{co-}\mathsf{NP}$?", thereby assuming a fact, we don't know.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy