7
$\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$
4
  • 1
    $\begingroup$ If I understand your question, it was asked (and answered) before in "Can strong NP-hardness really be shown using plain polytime reductions?" $\endgroup$
    – Jeremy
    Commented Jun 8, 2013 at 10:22
  • 1
    $\begingroup$ @Jeremy: Isn't this the wrong direction? What he asks is: "Why is $NP \subset P^{NP}$?" $\endgroup$
    – frafl
    Commented Jun 8, 2013 at 20:02
  • $\begingroup$ Hi @frafl, i assume you mean strict containment, that is, that the reverse inclusion does not hold. The "$\subset$" notation often doesn't mean strict containment but is just a synonym for "$\subseteq$", so i think you will confuse people -i thought you had made a mistake at first when reading your comment. $\endgroup$
    – plm
    Commented Aug 27, 2023 at 0:32
  • $\begingroup$ I add that the nonclosure of NP under Turing reduction is conjectural on P≠NP or just on NP≠coNP. It is conceivable that NP is closed under Turing reduction, or just that this is consistent with ZF, and then that it is also independent of ZF. $\endgroup$
    – plm
    Commented Aug 27, 2023 at 1:06

2 Answers 2

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 and acknowledge you have read our privacy policy.