Algorithms / Polynomial Reductions
Least You Need to Know: Polynomial Reductions, Direction, and Hardness Transfer
Reductions are directional proof tools. The whole point is to transform instances of a known problem into instances of a target problem so that solving the target would also solve the source, while preserving yes/no answers and staying polynomial-time.
The least you need to know
- A reduction `A <=_p B` means a polynomial-time solver for `B` would give a polynomial-time solver for `A`.
- To prove `B` is NP-hard, start from a known NP-hard or NP-complete problem `A` and reduce `A` to `B`.
- A reduction must preserve the answer: yes maps to yes and no maps to no.
- The reduction itself must run in polynomial time.
- Direction mistakes are among the most common exam errors.
Key notation
A <=_p B
problem `A` polynomial-time reduces to problem `B`
source
the known problem you start from
target
the problem whose hardness you want to prove
Tiny worked example
- To show **Subgraph Isomorphism** is hard, you can start from **Clique**.
- Map `(G, k)` to the pair `(K_k, G)`.
- Then `G` has a `k`-clique exactly when the pattern graph `K_k` appears as a subgraph of `G`.
- The reduction direction is from the known hard problem **Clique** to the target **Subgraph Isomorphism**.
Common mistakes
- If you reduce the new problem to an old hard one, you usually show the old one is no harder than the new one, which is the wrong direction for NP-hardness.
- A clever-looking transformation is useless if it does not preserve yes/no equivalence.
- Polynomial-time means the converter must itself be efficient.
How to recognize this kind of problem
- The prompt asks what a reduction direction proves.
- You need to transfer hardness from a known benchmark problem to a new problem.
- The main challenge is building a correct instance translation.