Gap-Introducing Reduction

Definition

Gap-Introducing Reduction

A gap-introducing reduction maps each instance of SAT in polynomial time to an instance of an optimisation problem . Fix a positive threshold function and a gap-factor function , where is the target encoding length. The thresholds used below must be computable and comparable in polynomial time.

Minimisation

For every , with ,

Maximisation

For every , with ,

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 . For maximisation, it never produces one whose optimum lies in .

This says nothing about arbitrary instances of : 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 .

An ordinary decision reduction may distinguish optima and . A factor- minimisation algorithm could return in the first case and in the second; these outputs do not separate the answers. A gap reduction instead puts the no-optimum strictly beyond , 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- approximation unless . A maximisation gap rules out a polynomial-time ratio- approximation under the same assumption.

Proof

Minimisation: inspect the returned feasible cost

A hypothetical approximation satisfies .

• If is satisfiable, then .
• If is unsatisfiable, then .

Thus decide SAT by testing . The yes-case uses the approximation guarantee; the no-case uses only feasibility.

Maximisation: inspect the returned feasible value

A hypothetical approximation satisfies .

• If is satisfiable, then .
• If is unsatisfiable, then .

Thus decide SAT by testing . 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 to and, for a fixed , guarantees

Here is the smallest vertex cover size. An -approximation returning a cover would decide SAT by testing .

For a numerical illustration, let and . The yes-optimum is at most , the no-optimum is greater than , and an approximate yes-cover has size at most .

This is a conditional illustration: the argument assumes such a construction, rather than supplying one. In particular, the assumed must be compatible with on no-instances; it cannot be an arbitrary constant greater than one.