Composition of Gap Reductions

Definition

Composition of Gap Reductions

Suppose is a gap-introducing reduction from SAT to a minimisation problem with threshold and factor . Suppose is a gap-preserving reduction from to a maximisation problem , with the same source threshold and factor , and target threshold and factor .

Then is a gap-introducing reduction from SAT to :

Consequently has no polynomial-time -approximation unless . Analogous compositions apply to the other objective directions.

Follow Each Case Through Both Maps

Write , , and . The important feature is not merely that the arrows connect: the middle inequalities must be exactly the premises needed by .

Proof

Satisfiable source formula

Because introduces the source gap, satisfiable gives . This is the yes-premise of , so .

Unsatisfiable source formula

Because introduces the source gap, unsatisfiable gives . This is the no-premise of , so .

Polynomial time and hardness

A polynomial-time computation of has polynomial output length. Running polynomial-time on that output still takes polynomial time in .

A hypothetical -approximation on returns a value in the yes-case. In the no-case, feasibility forces . Comparing with would decide SAT in polynomial time.

Why Matching Thresholds Matters

Suppose promises no-instances with , but preserves only no-instances with . A possible output with satisfies the first promise but not the second. We cannot apply the no-case implication of .

Exact equality of the middle parameters is sufficient. More generally, it is enough that each output range of is contained in the corresponding promised input range of .