P and NP — the two classes

Two categories of computing problem — and the line between them is the line that decides your engineering budget.

The two names are acronyms, and the words inside them are the whole idea. P stands for polynomial time — problems with a known algorithm whose runtime grows as a polynomial in the input size (n, n², n³ — never exponential). Doubling the input only multiplies the work by a predictable factor. Routing, sorting, matching, scheduling on one machine — all in P.

NP stands for nondeterministic polynomial time. The "nondeterministic" part is a piece of theoretical-computer-science jargon for a hypothetical machine that gets to guess the right path; the working definition that matters in a planning meeting is the equivalent one — NP is the class of problems whose candidate answers can be verified in polynomial time, even when finding the answer in the first place may take forever. Sudoku is the everyday example: checking a filled grid is trivial, filling an empty one is hard.

A common misread: NP does not mean "non-polynomial." Every P problem is also in NP — if you can solve it fast, you can certainly check it fast. Whether every NP problem is also in P (whether P = NP) is the most famous unsolved question in computer science. The working assumption — and the basis of every engineering plan — is that the two are different. Knowing which category a problem lives in determines whether the work is a week or a quarter.

A Sudoku checker is the canonical P-class function — it scans the grid once and decides. A solver is NP — searching for a valid grid is the expensive half. In Rust both are short, but only the checker is fast.

// O(n²) in the side length — the cheap half.
fn is_valid_sudoku(grid: &[[u8; 9]; 9]) -> bool {
    for i in 0..9 {
        let (mut row, mut col, mut box_) = ([false; 9], [false; 9], [false; 9]);
        for j in 0..9 {
            let (r, c) = (grid[i][j], grid[j][i]);
            let b = grid[(i / 3) * 3 + j / 3][(i % 3) * 3 + j % 3];
            for (v, seen) in [(r, &mut row), (c, &mut col), (b, &mut box_)] {
                if v == 0 { continue; }
                if seen[(v - 1) as usize] { return false; }
                seen[(v - 1) as usize] = true;
            }
        }
    }
    true
}

The dense line is the box-coordinate trick. The outer i does triple duty — row i, column i, AND box i — so one pair of nested loops checks all three groups at once. For the box, each box i sits at corner ((i/3)*3, (i%3)*3) and cell j inside it sits at offset (j/3, j%3). Add the corner and the offset and you have the absolute (row, col).

// Same expression, expanded into named pieces.
let box_row    = i / 3;           // 0..3 — which row of boxes
let box_col    = i % 3;           // 0..3 — which column of boxes
let corner_row = box_row * 3;     // top-left of that box
let corner_col = box_col * 3;

let cell_row   = j / 3;           // 0..3 — offset down inside the box
let cell_col   = j % 3;           // 0..3 — offset right inside the box

let row = corner_row + cell_row;
let col = corner_col + cell_col;
let b   = grid[row][col];
// Identical to: grid[(i / 3) * 3 + j / 3][(i % 3) * 3 + j % 3]

The layout makes the divmod obvious. A 9×9 grid is a 3×3 grid of 3×3 boxes; i selects a box, j selects a cell within it. Worked example below for i = 4, j = 5 — the middle box, cell 5 — which lands on absolute (4, 5).

         col 0 1 2 | 3 4 5 | 6 7 8
        ------+-------+-------+-------
row 0   |  .  .  .  |  .  .  .  |  .  .  .
row 1   |  box 0    |  box 1    |  box 2
row 2   |  .  .  .  |  .  .  .  |  .  .  .
        +-----------+-----------+-----------
row 3   |  .  .  .  |  .  .  .  |  .  .  .
row 4   |  box 3    |  box 4  * |  box 5     ← i=4, j=5 lands here
row 5   |  .  .  .  |  .  .  .  |  .  .  .
        +-----------+-----------+-----------
row 6   |  .  .  .  |  .  .  .  |  .  .  .
row 7   |  box 6    |  box 7    |  box 8
row 8   |  .  .  .  |  .  .  .  |  .  .  .

i = 4 → box_row = 4 / 3 = 1   → corner_row = 1 * 3 = 3
        box_col = 4 % 3 = 1   → corner_col = 1 * 3 = 3
j = 5 → cell_row = 5 / 3 = 1
        cell_col = 5 % 3 = 2

absolute (row, col) = (3 + 1, 3 + 2) = (4, 5)

In plain terms

Almost every estimating error in engineering comes from misreading which category a problem belongs to. When the team treats a P-class problem as if it were NP — building elaborate heuristics, buying expensive solvers, hiring optimization specialists — the work takes weeks instead of an afternoon. When the team treats an NP problem as if it were P — promising an exact answer at scale, in real time, for free — the project misses every deadline and ships a bad approximation that nobody trusts.

The split is not about how hard the problem feels. It is about whether a known fast solution exists. A polynomial-time solution is one where the work grows predictably with the input — double the data, the work roughly doubles or quadruples, but it does not explode. These problems have been studied for decades, and almost every one has a named algorithm in a Rust crate that an engineer can drop in. Routing a delivery truck through a road network is P. Matching tutors to students by availability is P. Allocating ad slots to bidders with a fixed budget is P.

The other category — NP — covers problems where the only honest answer is "we will check candidate solutions until one works." Some of these have effective approximations. Some have solvers that work on most real inputs. Some are genuinely intractable beyond toy sizes. The Traveling Salesman problem — visit a list of cities in the shortest total tour — is the famous example.

The question P = NP asks whether every NP problem is secretly P, with an undiscovered fast solution. If so, every codebreaking system on earth fails the next day, and every operations research consultant retires. Almost nobody believes this is the world. The plan is to act as if the categories are real.

The book is a field guide to telling them apart.