Gap-Introducing Reduction

Definition

Gap-Introducing Reduction

A gap-introducing reduction maps each instance $F$ of SAT in polynomial time to an instance $I=f(F)$ of an optimisation problem $\Pi$. Fix a positive threshold function $g(I)$ and a gap-factor function $\gamma (n)$, where $n=|I|$ is the target encoding length. The thresholds used below must be computable and comparable in polynomial time.

Minimisation

For every $F$, with $\gamma (|I|)>1$,

$$\begin{array}{rl}F\text{ satisfiable}& ⟹\mathrm{OPT}(I)\le g(I),\\ F\text{ unsatisfiable}& ⟹\mathrm{OPT}(I)>\gamma (|I|)g(I).\end{array}$$

Maximisation

For every $F$, with $0<\gamma (|I|)<1$,

$$\begin{array}{rl}F\text{ satisfiable}& ⟹\mathrm{OPT}(I)\ge g(I),\\ F\text{ unsatisfiable}& ⟹\mathrm{OPT}(I)<\gamma (|I|)g(I).\end{array}$$

The two possible source answers force the target optimum into separated ranges. SAT may be replaced by another NP-hard decision problem, with its yes- and no-instances taking the same roles.

What Is Missing from the Gap?

For minimisation, the reduction never produces an instance whose optimum lies in $(g(I),\gamma g(I)]$. For maximisation, it never produces one whose optimum lies in $[\gamma g(I),g(I))$.

This says nothing about arbitrary instances of $\Pi$: they may have optima in those ranges. Nor does it forbid a poor feasible solution of a yes-instance from having a value inside the gap. The promise concerns the optimum of instances produced by $f$.

An ordinary decision reduction may distinguish optima $100$ and $101$. A factor-$1.2$ minimisation algorithm could return $120$ in the first case and $101$ in the second; these outputs do not separate the answers. A gap reduction instead puts the no-optimum strictly beyond $120$, so approximation error cannot hide the distinction.

Why the Gap Gives Inapproximability

A gap is wider than the allowed approximation error

A minimisation gap as above rules out a polynomial-time factor-$\gamma (|I|)$ approximation unless $P=NP$. A maximisation gap rules out a polynomial-time ratio-$\gamma (|I|)$ approximation under the same assumption.

Proof

Minimisation: inspect the returned feasible cost $v$

A hypothetical approximation satisfies $\mathrm{OPT}(I)\le v\le \gamma \mathrm{OPT}(I)$.

• If $F$ is satisfiable, then $v\le \gamma \mathrm{OPT}(I)\le \gamma g(I)$.
• If $F$ is unsatisfiable, then $v\ge \mathrm{OPT}(I)>\gamma g(I)$.

Thus decide SAT by testing $v\le \gamma g(I)$. The yes-case uses the approximation guarantee; the no-case uses only feasibility.

Maximisation: inspect the returned feasible value $v$

A hypothetical approximation satisfies $\gamma \mathrm{OPT}(I)\le v\le \mathrm{OPT}(I)$.

• If $F$ is satisfiable, then $v\ge \gamma \mathrm{OPT}(I)\ge \gamma g(I)$.
• If $F$ is unsatisfiable, then $v\le \mathrm{OPT}(I)<\gamma g(I)$.

Thus decide SAT by testing $v\ge \gamma g(I)$. Both the reduction and the hypothetical approximation run in polynomial time.

The strict no-case inequalities are what exclude the boundary approximation factor as stated. Different endpoint conventions can instead give hardness only for strictly better factors.

Example

A hypothetical gap for Minimum Vertex Cover

Suppose a polynomial-time map sends $F$ to $G=(V,E)$ and, for a fixed $\alpha >1$, guarantees

$$\begin{array}{rl}F\text{ satisfiable}& ⟹\mathrm{OPT}(G)\le \frac{2}{3}|V|,\\ F\text{ unsatisfiable}& ⟹\mathrm{OPT}(G)>\alpha \frac{2}{3}|V|.\end{array}$$

Here $\mathrm{OPT}(G)$ is the smallest vertex cover size. An $\alpha$-approximation returning a cover $C$ would decide SAT by testing $|C|\le \alpha (2|V|/3)$.

For a numerical illustration, let $|V|=60$ and $\alpha =6/5$. The yes-optimum is at most $40$, the no-optimum is greater than $48$, and an approximate yes-cover has size at most $48$.

This is a conditional illustration: the argument assumes such a construction, rather than supplying one. In particular, the assumed $\alpha$ must be compatible with $\mathrm{OPT}(G)\le |V|$ on no-instances; it cannot be an arbitrary constant greater than one.