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)
  • let us continue this discussion in chat – 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 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 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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.