[Solved]: Is a Karp–Levin reduction a Levin reduction?

Problem Detail: 

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.

Asked By : user26418

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35971

3.2K people like this

 Download Related Notes/Documents