# Can we construct a Karp reduction from a Cook reduction between NP problems?

We have had several questions about the relation of Cook and Karp reductions. It's clear that Cook reductions (polynomial-time Turing reductions) do not define the same notion of NP-completeness as Karp reductions (polynomial-time many-one reductions), which are usually used. In particular, Cook reductions can not separate NP from co-NP even if P $\neq$ NP. So we should not use Cook reductions in typical reduction proofs.

Now, students found a peer-reviewed work [1] that uses a Cook-reduction for showing that a problem is NP-hard. I did not give them full score for the reduction they took from there, but I wonder.

Since Cook reductions do define a similar notion of hardness as Karp reductions, I feel they should be able to separate P from NPC resp. co-NPC, assuming P $\neq$ NP. In particular, (something like) the following should be true:

$\qquad\displaystyle L_1 \in \mathrm{NP}, L_2 \in \mathrm{NPC}_{\mathrm{Karp}}, L_2 \leq_{\mathrm{Cook}} L_1 \implies L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$.

The important nugget is that $L_1 \in \mathrm{NP}$ so above noted insensitivity is circumvented. We now "know" -- by definition of NPC -- that $L_2 \leq_{\mathrm{Karp}} L_1$.

As has been noted by Vor, it's not that easy (notation adapted):

Suppose that $L_1 \in \mathrm{NPC}_{\mathrm{Cook}}$, then by definition, for all languages $L_2 \in \mathrm{NPC}_{\mathrm{Karp}} \subseteq \mathrm{NP}$ we have $L_2 \leq_{\mathrm{Cook}} L_1$; and if the above implication is true then $L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$ and thus $\mathrm{NPC}_{\mathrm{Karp}} = \mathrm{NPC}_{\mathrm{Cook}}$ which is still an open question.

There may be other differences between the two NPCs but co-NP.

Failing that, are there any known (non-trivial) criteria for when having a Cook-reduction implies Karp-NP-hardness, i.e. do we know predicates $P$ with

$\qquad\displaystyle L_2 \in \mathrm{NPC}_{\mathrm{Karp}}, L_2 \leq_{\mathrm{Cook}} L_1, P(L_1,L_2) \implies L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$?

1. On the Complexity of Multiple Sequence Alignment by L. Wang and T. Jiang (1994)
• – Raphael Jan 30 '14 at 15:15
• Is your question if $\mathrm{NPC}_{\mathrm{Karp}} = \mathrm{NPC}_{\mathrm{Cook}} \bigcap \mathrm{NP}$? – Albert Hendriks May 9 '18 at 5:41
• @AlbertHendriks Similar, but not the same. I'm asking for a predicate $P$ which your variant would set to "$L_1 \in \mathrm{NP}$" (cf. first part of the question), i.e. if there are results with $P$ stronger than NP-membership. – Raphael May 9 '18 at 8:26

its a generally open TCS problem subject to ongoing research whether & the exact conditions Cook & Karp reductions are equivalent and is apparently closely related to the open NP=?coNP question & other complexity class separations eg E=?NE (wrt sparse languages).

here are two research papers on the subject & further leads on tcs.se via similar question:

• I'm not looking for the exact relation. – Raphael Feb 5 '14 at 7:42

In general, to mechanically turning a Cook-complete problem into a Karp-complete problem, there must be something special with the language itself.

For example, even a much restricted version of Cook reduction, namely negative reduction (reduce to one instance like Karp does, ask for answer, then negate), would require something special in the language $$L$$ to be easily turn into a standard Karp reduction.

We can say that if $$L$$ has the following property:

Given any instance $$x$$, we can, in polynomial-time, produce $$x'=f(x)$$, such that $$L(x)\neq L(x')$$.

So we can have a standard Karp reduction by first reduce to $$g(x)$$ by a negative reduction, then output $$f(g(x))$$.

As you can see, these properties are not normally seen in complexity theory, computability theory. In conclusion, it is extremely unlikely to be able to turn Cook into Karp.