Gap promise problems and gap-preserving reductions

Fix a maximization problem in the finite-instance model of Optimization problems and approximation ratios and a scale function $M$ that assigns to every instance $x$ a positive rational $M(x)$, thought of as the count of the objects being optimized; for max-3SAT below the domain consists of formulas with at least one clause, $M(x)$ is the number of clauses, and the objective is the maximum number of simultaneously satisfied clauses.

For rationals with $0\le s<c$, the gap problem $\mathrm{Gap}(c,s)$ is the promise problem whose yes side consists of the instances $x$ with $\mathrm{OPT}(x)\ge cM(x)$ and whose no side consists of the instances with $\mathrm{OPT}(x)\le sM(x)$. Instances with $sM(x)<\mathrm{OPT}(x)<cM(x)$ lie outside the promise. Since $M(x)>0$ and the objective is nonnegative, both conditions are value inequalities and no quotient by $\mathrm{OPT}(x)$ is formed; in particular the case $\mathrm{OPT}(x)=0$ is covered by the no side whenever $s\ge 0$.

A gap-preserving reduction from a source promise problem to a target promise problem is a total function computable by a deterministic polynomial-time algorithm such that every source instance is carried into the target promise, every source yes instance is carried into a target yes instance, and every source no instance is carried into a target no instance. When the source is a language $L$, the same definition applies with yes side $L$ and no side its complement, in the sense of Polynomial-time many-one reductions; the target is then read as the indication that the constructed target instance satisfies the required side of its gap. Compositions of gap-preserving reductions are again gap-preserving reductions, the intermediate instance always lying in the target promise by construction.

The two gap reductions on this page use these fixed conventions. For max-3SAT the gap domain consists of formulas with $m\ge 1$ clauses, the scale is $m$, and the optimum is the maximum number of simultaneously satisfiable clauses. For maximum independent set the clause-literal reduction uses the number $m$ of clause clusters as its positive scale. The PCP reduction constructs a formula with at least one clause on every input, so its composition with the clause-literal reduction stays in these domains. The latter construction also preserves optimum values for the empty formula and its empty graph, but these zero-clause instances are outside the positive-scale gap domains.