I was reading about $L$-reductions and there was one part in the definition that I thought was interesting. I wanted to know what motivated people who came up with it to have it included in the definition.
Recall that a problem $A$ is $L$-reducible to another problem $B$ if there exist polynomial-time computable functions $f$ and $g$, and positive constants $\alpha$ and $\beta$ such that:
- If $x$ is an instance of problem $A$, then $f(x)$ is an instance of problem $B$.
- If $y'$ is a solution to the instance $f(x)$ of problem $B$, then $g(y')$ is a solution to the instance $x$ of problem $A$.
- $OPT_B(f(x)) \leq \alpha OPT_A(x)$.
- $|c_A(g(y'))-OPT_A(x)| \leq \beta |c_B(y')-OPT_B(f(x))|$.
where $c_A$ and $c_B$ are the cost functions for the problems $A$ and $B$, and $OPT_A$ and $OPT_B$ have their usual meanings.
Points 1, 2, and 4 seem completely natural to me. We want some way to map instances of $A$ to instances of $B$ in polynomial time. $f$ takes care of that. Additionally, we want some way (again in polynomial time) to map solutions to instances of $B$ to solutions to instances of $A$. $g$ takes care of that. Finally, we want the mapped solutions to preserve some notion of "quality" so that we can make statements like "if $y'$ is a "good" solution, then $g(y')$ is not "too bad" of a solution". Point 4 takes care of that. But what do we need point 3 for? It seems to me that points 1, 2 and 4 suffice for the definition of a "natural" approximation-preserving reduction.
I know that for $L$-reducibility to imply $PTAS$-reducibility, we need point 3. But is that the only reason for adding point 3 to the definition?