5
$\begingroup$

My understanding is that Karp many-one reductions are more general than Levin many-one reductions, and that Levin many-one reductions must allow for the number of certificates for a problem $A$ reduced to $B$ to be recovered from a single oracle call giving the number of certificates for $B$.

So, what exactly is a Karp–Levin reduction? Quoting the paper "Witness Encryption and its Applications",

We now formally describe our encryption systems. For building them we will assume the existence of a witness encryption scheme for an NP-Complete language $L$ for which there exists a Karp–Levin reduction. We focus on presenting the constructions in this section and defer the proofs to Appendix A.

Other instances of "Karp–Levin" reductions can easily be found elsewhere.

From slide 11 of this presentation on PCPs by Mario Szegedy, it seems like a Karp–Levin many-one reduction is just a Levin many-one reduction. Is that correct?

Update: To explain why I am uncertain about Yuval Filmus' answer below, and why I'm asking this question, quoting from page 17-4 of the "Hardness of Approximation" chapter of the Handbook of Approximation Algorithms and Metaheuristics, a chapter written by Mario Szegedy (a Godel prize winner for his contributions to the PCP theorem),

Reduction is perhaps the most useful concept in algorithm design. Interesting, it also turns out to be the most useful tool in proving computational hardness [21-23]. When a problem $A$ Cook reduces to $B$, the hardness of $B$ follows form the hardness of $A$. Unfortunately, Cook reduction does not ensure that if $A$ is hard to approximate then $B$ is hard to approximate. For reducing hardness of approximation new definitions are necessary.

Let $F_1(x, y)$ and $F_2(x', y')$ be functions that are optimized for y and y' (maximized or minimized in an arbitrary combination). Let $OPT_1(x)$ and $OPT_2(x')$ be the corresponding optimums. A Karp–Levin reduction involves two maps:

  1. a polynomial-time map $f$ to transform instances $x$ of $OPT_1$ into instances $x' = f(x)$ of $OPT_2$ [Instance Transformation];
  2. a polynomial-time map $g$ to transform (input, witness) pairs $(x', y')$ of $OPT_2$ into witnesses $y$ of $OPT_1$ [Witness Transformation];

Observe that the witness transformation goes from $OPT_2$ to $OPT_1$. Let $opt_1 = OPT_1(x)$, $opt_2 = OPT_2(f(x))$, $appr_1 = F_1(x, g(f(x),y'))$, and $appr_2 = F_2(f(x),y')$.

So Yuval Filmus' answer below appears to only cover the "[Instance Transformation]" part of a Karp–Levin reduction, and not the "[Witness Transformation]" part, which seems to be interpretable as a way to recover certificates from some problem $A$ in $NP$ reduced to $B$ in $NP$ provided the number of certificates for $B$.

Am I off the mark here? And how is a Karp–Levin reduction different from a Levin reduction?

If there is non-standard terminology, or if definitions are supposed to be "understood" depending on whether one is talking about reductions among perhaps counting problems where witness transformations matter, please understand that this is intimidating for someone coming from outside of computer science! People's patience here is very much appreciated.

$\endgroup$
1
$\begingroup$

A Karp reduction from a language $A$ to a language $B$ is a function $f$ such that $x \in A$ iff $f(x) \in B$. This is the common meaning of the term.

David Richerby mentions in a comment below that Levin reductions are a more elaborate type of reductions: see this question.

In the present instance, Karp–Levin reduction seems to mean the same as Levin reduction. Indeed, since the common term for the usual notion of many-one reduction is Karp reduction, adding Levin's name might signify something different. The way the term is used in the paper should make it clear which meaning is being used. The paper might also include a definition of this somewhat non-standard term, and I suggest you include such a definition in future papers you may write.

$\endgroup$
  • $\begingroup$ This definition and answer contradict the much more detailed ones here. $\endgroup$ – David Richerby Jan 5 '15 at 12:25
  • $\begingroup$ @DavidRicherby The definitions detailed there are non-standard in my book. We can all agree that Karp–Levin reduction or Karp reduction mean what I wrote; Levin reduction, which is a term I never saw, probably means something else. $\endgroup$ – Yuval Filmus Jan 5 '15 at 12:26
  • $\begingroup$ @YuvalFilmus Please see my response in the question posting. $\endgroup$ – user26418 Jan 5 '15 at 15:48
  • $\begingroup$ @user26418 Use your common sense. From your quotes it is clear that Karp–Levin reduction means in this case Levin reduction. Otherwise there would be no need to mention that an NP-complete language with such a reduction is needed; all NP-complete languages have many-one reductions. Cook (or Turing, or oracle) reductions also don't cover witness transformations, and are an altogether different matter. $\endgroup$ – Yuval Filmus Jan 5 '15 at 15:52
  • $\begingroup$ @YuvalFilmus So anything covering "witness transformations" is a special kind of a Levin reduction? Instance (2) in my earlier question (cs.stackexchange.com/questions/35964/…) what would you call that? Isn't that a Cook reduction that allows certificates to be recovered for some problem $A$ in $NP$ from some problem $B$ in $NP$ with an oracle call + extra computation via a polynomial time procedure? $\endgroup$ – user26418 Jan 5 '15 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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