A Reduction Transfers Hardness, Not Weakness

The tempting inference is simple: Subset Sum is weakly NP-hard, and Subset Sum reduces to ILP, so perhaps ILP must also be weakly NP-hard. The first two facts are correct. The conclusion is not.

The arrow gives a lower bound

A polynomial-time reduction

says that an algorithm for can solve after translating the input. Therefore,

The conclusion is at least NP-hard. The reduction supplies no upper bound on . In particular, the adjective weak does not travel along the arrow.

The target has more room

The reduction maps source instances into only part of the target’s instance space:

Those translated instances may capture hardness caused by large binary numbers. The target may also contain other instances whose hardness survives even when every number is small. A reduction from a weakly NP-hard problem does not inspect or rule out this additional structure.

To classify as weakly NP-hard, one needs more than an NP-hardness reduction. One must also show the tractable side of the claim, typically a pseudo-polynomial algorithm or polynomial-time solvability under unary encoding.

ILP needs the second reduction

The Subset Sum reduction to ILP uses coefficients . Their binary magnitude carries the source problem’s weak hardness. This proves ordinary NP-hardness, but says nothing against stronger hardness.

The Vertex Cover reduction to ILP uses only binary variables, coefficients from , and a bound . The numbers remain small, yet the reduction is still NP-hard. This establishes strong NP-hardness.

The corrected mental model is directional: a reduction tells us how low the target cannot fall. It does not tell us how much higher the target’s hardness may rise.