18
$\begingroup$

The notion of polynomial time reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using an algorithm for a different problem.

However, in the theory of $\mathcal{NP}$-completeness, the notion of $\mathcal{NP}$-hardness is captured via mapping reductions (Karp reductions). This concept of "restricted" reductions is much-less intuitive (at least to me). It even seems a bit contrived, as it creates a somewhat less intuitive notion of hardness; by that I'm referring to the fact that $\mathcal{NP}$ does not trivially contains $co-\mathcal{NP}$. Although in complexity theory we are very used to the concept that being able to solve a problem such as $\mathsf{SAT}$ does not imply that we can solve $\overline{\mathsf{SAT}}$, in natural settings (which are captured by Cook reductions), assuming we have an algorithm for solving $\mathsf{SAT}$, we can solve $\overline{\mathsf{SAT}}$ just by running the algorithm for $\mathsf{SAT}$ and returning the opposite.

My question is why should we use Karp reductions for the theory of $\mathcal{NP}$-completeness? What intuitive notion does it capture? How does it relates to the way we understand "hardness of computation" in the real world?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ agreed that the basic defn of Cook and Karp reductions are not very transparent & subtle and not at all apparent in their distinction early on. you are not alone.. the wikipedia article on Ptime reduction is currently marked as "possibly confusing or unclear to readers" and many one reduction is not a lot better... on the other hand they do answer some of the basic questions similar to yours... $\endgroup$
    – vzn
    Nov 19, 2012 at 17:31
  • 2
    $\begingroup$ see also (near duplicate) Many-one reductions vs. Turing reductions to define NPC $\endgroup$
    – vzn
    Nov 19, 2012 at 17:34

2 Answers 2

Reset to default
18
$\begingroup$

Like Turing reductions, many-one reductions came into complexity theory from computability/recursion theory literature. Cook and Karp reductions are natural complexity theoretic versions of similar existing reductions in computability.

There is a intuitive way of explaining many-one reductions: it is a restriction of Turing reductions where we can ask only a single question from the oracle and the oracle's answer will be our answer.

Now the question is why would we need to study this (and any other kind of reductions like truth-table, weak-truth-table, etc.)?

These reductions give a finer picture than Turing reductions. Turing reductions are too powerful to distinguish between many concepts. A very large portion of computability theory is devoted to the study of c.e./r.e. degrees. The notion of an c.e. set is central. We can have TM machine that can enumerate an infinite set, we may not be able to enumerate its complement. If you want to study c.e. sets then Turing reduction is too strong since c.e. sets are not closed under it. So many-one reductions are a (and maybe the) natural way of defining reductions for this purpose.

Other types of reductions are defined for similar reasons. If you are interested I would suggest checking Piergiorgio Odifreddi's "Classical Recursion Theory". It has a quite comprehensive chapter on different reductions and their relations.

Now for complexity theory the argument is similar. If you accept that $\mathsf{NP}$ is a extremely natural class of problems and you want to study $\mathsf{NP}$, then Cook reductions are too strong. The natural choice is a weaker reduction such that $\mathsf{NP}$ is closed under it and we can prove existence of a complete problem w.r.t. to those reduction for $\mathsf{NP}$. Karp reductions are the natural choice for this purpose.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ ?? "cook reductions are too strong" to study NP? what do you mean by that? think it could be phrased a little clearer/better $\endgroup$
    – vzn
    Nov 20, 2012 at 19:11
-5
$\begingroup$

there are several questions on this site related to Cook vs Karp reductions. have not seen a very clear description of this for the neophyte because its somewhat inherently subtle in many ways and its an active/open area of research. here are some refs that may be helpful to address it. as wikipedia summarizes, "Many-one reductions are valuable because most well-studied complexity classes are closed under some type of many-one reducibility, including P, NP, L, NL, co-NP, PSPACE, EXP, and many others. These classes are not closed under arbitrary many-one reductions, however."

it seems fair to say that even advanced theorists are actively pondering the exact distinction and differences as in below refs and the full story wont be available unless important open complexity class separations are resolved, ie these questions seem to cut to the center of the known vs unknown.

[1] Cook versus Karp-Levin: Separating Completeness Notions If NP Is Not Small (1992) Lutz, Mayordomo

[2] Are Cook and Karp Ever the Same? Beigel and Fortnow

[3] More NP-Complete Problems (PPT) see slides 9-14 on history & Cook vs Karp reduction distinctions

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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