P 的典型成員（canonical members of P）

一個由執行時間不等式定義的類別可能讓人覺得抽象，所以讓 P 變具體的最好辦法，就是去認識它的住戶。好消息是 P 裡滿是計算的日常主力——你絕不會稱為奇異的問題。看著它們聚在同一個屋簷下，能把 P 從一個定義變成一個有熟悉天際線的地方，並顯示「多項式時間」涵蓋了一大片真正有用的計算。

這是典型的巡禮，每個都附上把它放進 P 的那種演算法。圖的可達性（是否存在從 s 到 t 的路徑？）由廣度或深度優先搜尋在 O(n + m) 時間內解決。把 n 個項目排序，用合併排序或堆積排序是 O(n log n)。加權圖的最短路徑屈服於 Dijkstra 演算法（非負權重）或 Bellman-Ford，皆在多項式時間。最大匹配——盡可能完整地把相容項目配對——有多項式演算法（二部圖用 Hopcroft-Karp，一般情形用 Edmonds 的花朵演算法）。質數判定——決定一個以二進位寫下的數是否為質數——因 AKS 演算法而屬於 P。而線性規劃——在線性限制下最佳化一個線性目標——透過橢球法與內點法屬於 P（儘管流行的單純形法在最壞情況下是指數級的）。

這些例子不只是讓人安心；它們是 P 為「高效」之正確理想化的證據，因為我們實際在大規模下解決的問題不斷落在它裡面。它們也磨利了引向下一章的對比：這裡每一個都有已知的多項式演算法，而那些著名的 NP 完全問題（SAT、旅行推銷員巡迴、圖著色）則頑強抵抗，沒有已知的多項式演算法，且強烈懷疑根本不存在。這份清單與那份清單之間的界線，就是 P 對 NP 的實務面貌。