固定參數可解（fixed-parameter tractability, FPT）

許多重要問題是 NP 困難的，所以對「所有」輸入都快的演算法目前未知。但「困難」往往藏起了難度真正所在之處。以頂點覆蓋為例：找出 k 個頂點，碰到圖的每一條邊。暴力法試遍所有子集——毫無希望。然而實務上我們常只在意「小」的覆蓋：是否存在大小為 k 的覆蓋，其中 k 很小（例如 10），即便圖很巨大？固定參數可解的想法，就是把這樣一個參數 k 隔離出來，要求一個演算法把爆炸限制在 k 之內，而無論整體規模 n 多大都保持高效。

精確地說，一個參數化問題若能在 f(k) * n^c 時間內解出，就是固定參數可解的，其中 n 是輸入規模、k 是所選參數、c 是與 k 無關的常數，而 f 是「任何」只依賴 k 的函數——甚至像 2^k 這樣的指數。關鍵在於「分離」：無法避免的指數爆炸被隔離在 f(k) 裡並以「相乘」方式出現，而非進入 n 的指數。所以若 k 小，f(k) 是個可控的常數，執行時間本質上對 n 是多項式的。比較 2^k * n（FPT，k 小時極佳）與 n^k（「不是」FPT——指數本身隨 k 成長，所以即使 k=10 在大圖上也毫無希望）。頂點覆蓋是招牌例子：它有一個簡單的 2^k * n 演算法，透過有界搜尋樹——任取一條邊，它的兩端點至少一個必在覆蓋中，於是分兩支遞迴、k 減 1，得到深度為 k 的樹。

FPT 之所以重要，是因為它給出比「P 對 NP 困難」更細緻、更誠實的難度地圖：它解釋了為何許多 NP 困難問題實務上常被解出——它們的困難實例需要大的參數，而真實實例往往沒有。樹寬、解的大小、群集數都是常見參數。誠實的提醒：f(k) 可能大得天文（2^(2^k) 仍是「FPT」但毫無用處），所以 FPT 是理論上的效率類，不是速度的保證；並非每個參數化問題都是 FPT（W-階層分類了很可能「非 FPT」的問題，例如找 k-團，相信約需 n^k）；而這個好處完全取決於參數真的小。