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

Question

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)

Answer 1

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:

• Are Cook and Karp Ever the Same? Beigel, Fortnow

• Cook vs. Karp-Levin: Seperating Completeness Notions If NP Is Not Small (1995) Lutz, Mayordomo

• many one reductions vs Turing reductions to define NPC, tcs.se

Answer 2

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.