參數化複雜度（parameterized complexity）
古典複雜度問一個鈍直的問題：執行時間如何隨輸入大小 n 成長？但兩個輸入大小相同的 NP 困難問題，在實務上可能感覺天差地遠，因為真正使它們困難的，是某個小小的額外量。參數化複雜度精煉了這個問題：它把輸入大小 n 與第二個「參數」k 分開——k 度量輸入中造成困難的那部分——並追問：能否把爆炸限制在 k 身上。
核心的好消息是固定參數可解（FPT）。若一個問題能在 f(k) 乘以 n 的某個多項式的時間內解出——其中 f(k) 可以很龐大（甚至對 k 呈指數），但對輸入大小 n 的依賴維持多項式，且 k 不進入 n 的指數——它就是 FPT。當 k 很小時，回報是巨大的：只要 k 適中，f(k) 乘以 n 即使對很大的 n 也很快。把暴力的 n^k（k 坐在 n 的指數上，隨輸入增大而爆炸）與 FPT 的 2^k 乘以 n（指數被鎖在那個小參數上）對比。並非每個問題都是 FPT；W 階層（W[1]、W[2]……）為那些看似非 FPT 的問題分類，其中 W[1] 困難扮演「大概不是固定參數可解」的角色，正如 NP 困難示意「大概不是多項式」。
這是現代複雜度中最富實務成果的分支之一，因為真實輸入常有很小的自然參數：要刪除的變數數目、網路的樹寬、你願意接受的解的大小。頂點覆蓋是招牌例子——尋找大小為 k 的覆蓋是 FPT（可在約 2^k 乘以多項式時間內解出），所以只要你只想找小的覆蓋，即使在龐大的圖上也很容易。這個框架把粗糙的「NP 困難，放棄吧」轉成更銳利的「一般情況下 NP 困難，但當這個特定參數很小時可解」。
k-頂點覆蓋：某圖是否有 k 個頂點構成的覆蓋？樸素搜尋會試遍所有子集，毫無希望。FPT 的訣竅是：挑任一條邊；它的兩個端點之一必定在覆蓋裡，於是分成兩種情形並把 k 減 1 後遞迴。這棵分支樹深度為 k、寬度為 2，得到約 2^k 乘以多項式的時間——即使在百萬節點的圖上，k = 10 也很快。
FPT 把指數爆炸鎖在小參數 k 上，使對輸入大小的依賴維持多項式。
FPT（f(k) 乘以 n 的多項式）才是嚴格的目標；一個以 n^k 執行的演算法並非固定參數可解——即使對每個固定的 k 它都是多項式，因為 k 坐在 n 的指數上，成本會隨輸入增大而爆炸。