Reducibility — turning one problem into another

The most leveraged move in engineering is recognizing your new problem is an old problem in disguise.

A reduction is a translation from one problem to another such that solving the translated version solves the original. If you can translate your problem into a known-solved problem cheaply, you inherit that problem's solution and never have to write your own. This is the most leveraged move in engineering — and the most under-used one. An assignment problem ("match drivers to deliveries minimizing total miles") is a reduction away from a published algorithm with a Rust library that handles thousands of items in milliseconds. A constraint problem ("each shift must have at least two staff, no person works two shifts back-to-back") is a reduction away from a solver that the industry already built. When your team faces a new problem, the first question is not "what should we build" — it is "what known problem is this in disguise."

Driver-to-delivery assignment is the canonical assignment problem in disguise. The reduction is mechanical — build a cost matrix, hand it to a solver from pathfinding, read the matching back. No new algorithm to write.

use pathfinding::kuhn_munkres::kuhn_munkres_min;
use pathfinding::matrix::Matrix;

fn assign_drivers(miles: Vec<Vec<i32>>) -> Vec<usize> {
    let m = Matrix::from_rows(miles).expect("rectangular");
    let (_total, assignment) = kuhn_munkres_min(&m);
    assignment // assignment[driver] = delivery
}

02

The function is called kuhn_munkres_min — a stack of two surnames you probably have not seen on an algorithm before. Harold Kuhn published the method in 1955; James Munkres refined the analysis in 1957. The rest of the world calls it the Hungarian algorithm because Kuhn rediscovered an idea from two Hungarian mathematicians of the 1930s (Dénes Kőnig and Jenő Egerváry) and credited them in the name. Three names, one algorithm — papers say "Hungarian," textbooks say "Kuhn-Munkres," the Rust crate uses the historical-receipt version.
```
// One algorithm, four people, three names:
//   1931  Kőnig      (Hungary) — duality theorem
//   1932  Egerváry   (Hungary) — algorithmic refinement
//   1955  Kuhn       (US)      — "The Hungarian Method"
//   1957  Munkres    (US)      — polynomial-time analysis
//
// Papers call it the Hungarian algorithm.
// Crates call it kuhn_munkres.
use pathfinding::kuhn_munkres::kuhn_munkres_min;
```

A Matrix is a rectangular grid of numbers — rows × columns, every row the same length. Here each row is a driver and each column is a delivery, and the cell at (driver, delivery) is the cost (miles) of that pairing. Matrix::from_rows takes a Vec<Vec<i32>> (a list of equal-length lists) and turns it into a real matrix with row/column accessors. .expect("rectangular") makes the function panic loudly if the rows are not all the same length — a matrix has no room for a ragged input.

//          delivery 0   delivery 1   delivery 2
//        ┌─────────────────────────────────────────┐
// driver 0│      12           8           20       │
// driver 1│       9          15           11       │
// driver 2│      14          10            7       │
//        └─────────────────────────────────────────┘
//
// Cell (1, 2) = 11 means driver 1 → delivery 2 costs 11 miles.
let miles = vec![
    vec![12,  8, 20],
    vec![ 9, 15, 11],
    vec![14, 10,  7],
];
let m = Matrix::from_rows(miles).expect("rectangular");

// starts a line comment in Rust — everything after the two slashes, until the end of that line, is ignored by the compiler. It is a note to the reader, not code. The trailing note // assignment[driver] = delivery describes the shape of the return value: assignment is a Vec<usize> where the index is the driver number and the entry at that index is the delivery they were assigned to. So if assignment[1] == 2, driver 1 is going on delivery 2.

// "//" starts a line comment — everything after it on the same
// line is ignored by the compiler.  Notes to the reader, not code.

let assignment = vec![0, 2, 1];   // index = driver, value = delivery
//                    ^  ^  ^
//                    │  │  └── driver 2 → delivery 1
//                    │  └───── driver 1 → delivery 2
//                    └──────── driver 0 → delivery 0

// Look up which delivery driver 1 got:
let d = assignment[1];   // d == 2

In plain terms

Reductions are the secret superpower of experienced engineers. Most novel-looking business problems are not novel at all — they are a decades-old textbook problem with the words changed. "Find which customers to assign to which sales reps" is the assignment problem from 1955. "Decide which features to ship under a fixed engineering budget" is knapsack from 1957. "Plan our delivery routes" is vehicle routing from the 1960s. In every case, an experienced engineer recognizes the underlying shape and reaches for a library or a paper instead of building from scratch.

The translation step matters because once you have done it, you inherit decades of research. Someone has published the algorithm. Someone has implemented it as a library. Someone has benchmarked it on instances ten times the size of yours. The work has already been done. Your job is to phrase the problem in the right vocabulary.

In the other direction, reductions are also how we know certain problems are genuinely hard. Hundreds of business problems — scheduling, routing, packing, allocating — have been shown to be reducible to each other, all sitting in the same difficulty class. If one of them turns out to be easy, all of them do. So far, none of them has. That cluster of mutually-equivalent hard problems is called NP-complete, and the inability to crack any one of them after fifty years of effort is the strongest evidence that the cluster is genuinely hard.

The discipline to develop: in any planning meeting, when a new problem comes up, the first thirty minutes belong to "is this actually a known problem." More often than not, it is.

The biggest cost savings come not from clever code but from recognizing you do not need clever code.