# Why are $L$-reductions defined the way they are?

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:

1. If $$x$$ is an instance of problem $$A$$, then $$f(x)$$ is an instance of problem $$B$$.
2. 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$$.
3. $$OPT_B(f(x)) \leq \alpha OPT_A(x)$$.
4. $$|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?

• It seems that your question already contains a complete answer. – Yuval Filmus Sep 30 '20 at 15:23
• @YuvalFilmus, Ah, so the motivation for $L$-reductions is to have an easy-to-work-with reduction that also implies PTAS-reducibility? – mursalin Sep 30 '20 at 15:38
• That sounds like a good motivation. I don't know whether that was the original motivation, but it seems likely. – Yuval Filmus Sep 30 '20 at 15:46