除了 n 以外的第二個旋鈕
到這裡，你已見過對 NP 困難問題的三種誠實回應。複雜度那一階教過你，NP 完全意味著「目前不知道」有多項式演算法——而非「證明了沒有」——所以我們選擇應對，而不是投降。近似那一階用「精確」換來一個可證明的倍率。本階前面幾篇則用「完整資訊」換來一扇小窗：線上演算法在不知道未來的情況下決策，串流草圖在看不到整份輸入的情況下決策。參數化複雜度沿著一條全然不同的軸線去交換：它保留確切答案、也保留整份輸入，卻對「難處究竟藏在哪」問了一個更銳利的問題。
關鍵的洞見是：單靠一個數字「輸入規模 n」太過粗鈍。兩張 n 相同的圖，難度可能天差地別。所以我們引入一個第二個旋鈕，一個參數 k，挑來捕捉「讓某個實例變難」的結構。對於尋找小的頂點覆蓋——一組碰到每條邊的頂點——最自然的旋鈕，就是覆蓋大小 k 本身：實務上你往往只在乎是否存在一個很小的覆蓋（比方 k = 10），即使圖有上百萬個頂點。問題不再是「頂點覆蓋有多難？」，而變成「當 k 很小時，頂點覆蓋有多難？」
為什麼這個問題會有不同的答案？因為一個慢的演算法，可以用兩種非常不同的方式慢。暴力法把所有大小為 k 的子集都試一遍——大約有 n^k 個，而這個 n^k 是致命的：即使 k = 10、在一張百萬頂點的圖上，那也是「百萬的十次方」，毫無希望。本篇整場遊戲，就是把那份爆炸從 n 身上挪走、單獨放到 k 上——付 2^k，而不是 n^k。當指數騎在小旋鈕上、而非大旋鈕上，一個看似不可能的問題就變得稀鬆平常。
定義：指數騎在哪裡
一個參數化問題若能在 f(k) * n^c 的時間內解決，就稱為固定參數可解——FPT——其中 n 是輸入規模，k 是所選參數，c 是一個不依賴 k 的常數，而 f 是任何僅與 k 有關的函數——它可以狂野地像 2^k、甚至 2^(2^k) 那樣成長。這個定義的全部內涵，就濃縮在一個詞裡：隔離。那份無可避免的指數被隔離進 f(k) 裡，在那兒它只是個乘上去的因子，並被禁止進入 n 的指數。把這兩種形狀並排來讀，差別就是整門學問。
把這兩種形狀拿去對上真實數字。取 k = 10、在一張 n = 1,000,000 的圖上。FPT 形狀 2^k * n 是 1024 * 1,000,000，約 10^9——不到一秒。暴力形狀 n^k 是 (10^6)^10 = 10^60——宇宙熱寂級的時間。這道算術就是全部寓意：在 2^k * n 裡，指數騎在小旋鈕 k 上，所以一旦 k 固定，f(k) 不過是擺在前頭的一個常數；在 n^k 裡，參數已經爬進了 n 自己的指數，所以即使 k = 10，在大圖上也毫無希望。FPT 堅持指數騎在 k 上、絕不騎在 n 上。
請注意，2^k * n 與 n^k 都是「指數的」，可是對一個大圖上的小 k，它們相差五十個數量級。這就是 FPT 追逐的獎賞——而它和近似那一階追的，是個確實不同的獎賞。在那裡，對頂點覆蓋，我們接受一個至多兩倍最佳值的覆蓋，但在每個實例上都跑多項式時間。在這裡，我們要求確切的最小覆蓋，卻只在 k 小的時候才承諾有效率。兩種應對策略、兩種不同的犧牲：近似放棄精準度以在處處保有速度；FPT 保留精準度，並把成本關進一個你期望它很小的參數裡。
有界搜尋樹：在 2^k * n 內解頂點覆蓋
底下這個演算法把它落到實處，而它倚靠一個微小卻無可辯駁的觀察。隨便挑圖裡任一條邊 (u, v)。一個頂點覆蓋必須碰到這條邊，所以它必須包含 u、或 v、或兩者——沒有第四種選擇。這一個被迫的抉擇就是槓桿。我們分支：往一個方向試「u 在覆蓋裡」，往另一個方向試「v 在覆蓋裡」。無論走哪一支，我們都已把一個頂點押進覆蓋裡，可以把它（連同它的邊）從圖中刪去，留下一個更小的子問題，在其中我們改求一個大小為 k - 1 的覆蓋。這是分支定界法的一個聚焦版表親——對一個被迫的抉擇分支、在嚴格更小的預算上遞迴。
VC(G, k): if G has no edges: return YES # everything covered if k == 0: return NO # edges left but no budget pick any edge (u, v) return VC(G - u, k-1) OR VC(G - v, k-1) # branch: u in, or v in
現在來數成本，因為這正是魔術變成算術的地方。每次遞迴呼叫都把 k 恰好降 1，所以沒有任何一條遞迴路徑會超過 k 步——搜尋樹深度至多 k。每個節點分兩支，所以樹至多有 2^k 個葉子、總共約 2^k 個節點。在每個節點我們只做廉價的工：掃描找一條邊、刪一個頂點，全在 O(n) 時間內。相乘，整場搜尋花 O(2^k * n)。指數騎在 k 上，正如定義所要求。頂點覆蓋之所以是 FPT 的招牌寶寶，正是因為這個證明短得不可思議。
核心化：先縮小，再暴力
通往 FPT 還有第二條、互補的路，而它正合每個老練解題者的本能：在認真思考之前，先把那些被迫的部分劃掉。核心化把這份本能變成定理。它是一個多項式時間的前處理步驟，把任一實例縮成一個等價的實例——是非答案相同——其大小僅由 k 單獨決定，無論原本多巨大。縮小後的實例稱為核心，而這份工是由化簡規則完成的：一些你必須證明安全、再反覆套用到不再改變為止的簡單簡化。
- 規則一（孤立頂點）：刪掉任何沒有邊的頂點。它什麼都覆蓋不到，因此對覆蓋永遠沒有幫助——移除它不改變任何答案，又縮小了圖。
- 規則二（高度數頂點）：若某頂點 v 有超過 k 個鄰居，它就必須在每個大小為 k 的覆蓋裡。倘若把它排除在外，它那 k+1 條以上的邊就各需要一個不同的覆蓋頂點——這已超過 k 個了。所以把 v 放進覆蓋，並把 k 減 1。
- 反覆套用兩條規則，直到都不再觸發。此時每個存活下來的頂點度數至多 k，而一個大小為 k 的覆蓋至多碰到 k * k = k^2 條邊。所以若剩下超過 k^2 條邊，立刻回答「否」；否則你手上握著一個至多 k^2 條邊的核心。
看看剛才發生了什麼：一張有上百萬條邊的圖，在多項式時間內被化簡成至多 k^2 條邊的圖——它的大小如今只依賴 k。在這個核心上跑任何精確方法（甚至就用那棵 2^k 搜尋樹，但現在是在一個極小的輸入上），你就完工了。而有一個漂亮的定理把這個圈收攏：一個參數化問題是 FPT，若且唯若它有核心化。所以本篇的兩條路並非對手，而是一枚硬幣的兩面——核心與固定參數可解性是等價的，而更小的核心意味著更快的求解。
樹寬、精確指數的表親，與那道牆
解的大小是最顯眼的旋鈕，但不是唯一的——而其中最深刻的一個是結構性的。許多在一般圖上 NP 困難的問題，在樹上卻很容易，因為樹沒有糾纏的環：你從葉子掃到根、把子答案合併起來，正是你已經會的樹上動態規劃。樹寬是一個衡量「一張圖離樹有多遠」的數字——真正的樹是 0 或 1，近似樹狀的圖很小，密密交織的圖很大。把樹寬 t 框住，你就能在一個樹分解上跑動態規劃，為每個小「袋子」裡那幾個頂點的每種行為記住一份部分答案，得出形如 f(t) * n 的執行時間。
注意那同一個 FPT 形狀，只是現在由 t 扮演 k 的角色：指數成本住在 f(t) 裡（每個袋子常約 2^t），而對 n 的依賴維持線性。這就是為什麼這麼多真實結構能帶來回報——結構化程式碼的控制流程圖、串並聯網路、以及許多真實世界的圖都有小樹寬，於是一大堆原本困難的性質（獨立集、支配集、著色）在它們之上變得可解。這和那棵搜尋樹是同一個把戲，只是透過結構、而非解的大小來看：找一個實務上很小的參數，並只在它身上付那份指數。
FPT 是精確指數演算法心態的近親：兩者都拒絕放棄最佳解，轉而搏鬥那份指數的形狀。Held-Karp 在 O(2^n * n^2) 內解決 TSP——比 n! 好得驚人——而分支化簡能在約 1.2^n 內解出獨立集。差別在於攻擊的軸線：精確指數演算法壓低 n 指數的底數（把 2^n 往 1.3^n 壓），而 FPT 把指數整個從 n 挪到參數 k 上。同樣拒絕失去精準度，兩種讓「無可避免的爆炸」變得能熬過去的不同辦法。
最後，是那道誠實的牆。並非每個參數化問題都是 FPT。尋找大小為 k 的團（clique）看起來和頂點覆蓋騙人地相似，可是已知最好的演算法仍要大約 n^k——指數頑固地黏在 n 上。參數化複雜度有自己的困難性理論，W 階層，它把這類問題歸類為「很可能不是 FPT」，正如 NP 完全把問題歸類為「很可能不是多項式的」。所以「挑個參數你就贏了」是錯的；那參數必須是對的那一個，而即便如此，有些問題仍頑抗。還要記得 f(k) 可以是 2^(2^k)——依定義仍算「FPT」，實務上卻沒用。FPT 給出一張比「P 對 NP 困難」更細緻、更誠實的難度地圖，但和本階每件工具一樣，它只有在它的假設——一個確實很小的參數——真正成立時，才掙得它的威力。