canonical members of P

A class defined by an inequality on running time can feel abstract, so the best way to make P concrete is to meet its residents. The good news is that P is full of the everyday workhorses of computing, problems you would never call exotic. Seeing them gathered under one roof turns P from a definition into a place with a familiar skyline, and shows that 'polynomial time' captures a huge swathe of genuinely useful computation.

Here is the canonical tour, each with the kind of algorithm that puts it in P. Graph reachability (is there a path from s to t?) falls to breadth-first or depth-first search in O(n + m) time. Sorting n items is O(n log n) by merge sort or heapsort. Shortest paths in a weighted graph yield to Dijkstra's algorithm (with non-negative weights) or Bellman-Ford, in polynomial time. Maximum matching, pairing up compatible items as fully as possible, has polynomial algorithms (Hopcroft-Karp for bipartite graphs, Edmonds' blossom algorithm in general). Primality, deciding whether a number written in binary is prime, is in P thanks to the AKS algorithm. And linear programming, optimising a linear objective under linear constraints, is in P via the ellipsoid and interior-point methods (even though the popular simplex method is worst-case exponential).

These examples do more than reassure; they are the evidence that P is the right idealisation of efficient, because the problems we actually solve at scale keep landing inside it. They also sharpen the contrast that motivates the next chapter: every one of these has a known polynomial algorithm, whereas the celebrated NP-complete problems (SAT, the travelling salesman tour, graph colouring) stubbornly resist, with no polynomial algorithm known and a strong suspicion none exists. The line between this list and that one is the practical face of P versus NP.