#StackBounty: #complexity-theory #reductions #approximation Why gap preserving reduction is weaker than L-reduction?

Bounty: 50

In Vizirani’s textbook says in page 332,

Gap preserving reductions are weaker than their L-reductions […] one of the motivations for the PCP theorem was that establishing an inapproximability result for MAXSAT would directly yield inapproximability results for all Max-SNP-hard problem.

Now my question is: Why Gap preserving reduction is weaker than L-reduction? as a person to prove a reduction, then Gap reduction is better than L-reduction to give lower bound. Moreover, Gap reduction gives you better result than L-reduction (e.g. vertex cover is inapproximable with number close to $1.3 – epsilon$ using Gap-reduction while using L-reduction there is no known “as far as I know” reduction that gives inapproximable even less than 2. So, it seems for me that Gap-reduction is better, and thus it is stronger than L-reduction in terms of given lower bounds. Now, why he says “Gap preserving reduction is weaker than L-reduction?” or may be he means something else, then could you explain to me.

Or does he mean the following:
suppose we have two reductions: Reduction A, B. Then, A is better than B if B in included in the A as subset (so A is big class and B is small and subset of A). In this case, A will give better bound (;because it is bigger while B gives not better than A because it is smaller). Is this what he means?! [in this case A=gap reduction, B=L-reduction].


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.