Is a <PERSON>-Levin reduction a <PERSON> reduction?
My understanding is that <PERSON> many-one reductions are more general than <PERSON> many-one reductions, and that <PERSON> 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 <PERSON>-Levin reduction? Quoting this paper "Witness Encryption and its Applications - https://eprint.iacr.org/2013/258.pdf
"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 "<PERSON>-Levin" reductions can easily be found.
From slide 11 here http://www.cs.rutgers.edu/~szegedy/11596/PCP-1.pdf it seems like a <PERSON>-Levin many-one reduction is just a <PERSON> many-one reduction?
To explain why I am uncertain about <PERSON> 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 <PERSON> (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$ <PERSON> reduces to $B$, the hardness of $B$ follows form the hardness of $A$. Unfortunately, <PERSON> reduction does not ensure that if $A$ is hard to approximate then $B$ is hard to approximate. 603
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 <PERSON> answer below appears to only cover the "[Instance Transformation]" part of a <PERSON>-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 <PERSON>-Levin reduction different than a <PERSON> 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. 603