精確指數演算法（exact exponential algorithms）
有些問題是 NP 困難的，所以（除非 P = NP）每個在所有輸入上都「精確」解它們的演算法，在最壞情況下都必須花指數時間。許多應對方式放棄精確——近似、啟發式、隨機化。精確指數演算法拒絕這麼做：它們堅持可證明正確、最佳的答案，轉而努力讓那無法避免的指數成長得盡可能慢。目標不是逃離指數時間，而是縮小它的底數——把毫無希望的 2^n 變成「僅僅困難」的 1.3^n，這可能是「能解 n = 40」與「能解 n = 100」之間的差別。
許多問題的基準是暴力法：試遍所有 2^n 個子集、所有 n! 種排列。精確指數演算法靠巧思打敗這個基準，同時保住正確性。三種招牌技術：(1) 子集上的動態規劃——Held-Karp 演算法以 O(2^n * n^2) 而非 O(n!) 解旅行推銷員問題，方法是為每個城市子集與每個端點，記住「恰好走訪該子集的最佳路徑」；對大 n 而言 2^n 比 n! 小得天文。(2) 分支與化簡（branch-and-reduce）——對一個選擇分支，但用化簡規則讓每支大幅縮小實例，可證明地把底數壓到 2 以下（獨立集可在約 1.2^n 內解出）。(3) 排容原理與折半相遇，把搜尋一分為二以從指數開根號（藉由解兩半再合併，把 2^n 變成約 2^(n/2)）。每種都在降低成長常數的同時保住精確保證。
精確指數演算法之所以重要，是因為有時你真的需要最佳解而非近似——驗證硬體、解小而關鍵的排程或路由實例、或證明一個組合事實——而那些輸入雖在一般情況下 NP 困難，卻小到「更小的底數」就讓它們變得可行。它們也加深了我們對「指數成本究竟從何而來」的理解。誠實的提醒：這些仍是指數的，所以只在不大的 n 上有幫助（把底數從 2 降到 1.3 大概多買你 2-3 倍的輸入，不是無限擴展）；更小的底數並不會讓問題變多項式；而降低底數往往付出大的多項式因子或記憶體（Held-Karp 需要 2^n 記憶體），所以實際的好處必須逐案權衡。
用 Held-Karp 解旅行推銷員：不去測試所有 n! 條巡迴路線，而是建一張表 dp[S][j] = 從城市 1 出發、恰好走訪集合 S、結束於城市 j 的最短路徑。藉由試遍每個可能的前一城來填它。它以 O(2^n * n^2) 時間與 2^n 記憶體執行——對 n = 20，2^20（約一百萬）很容易，而 20!（約 2.4 * 10^18）不可能。同樣的精確答案，底數小得多。
保住精確；縮小指數底數（n! -> 2^n，或 2^n -> 1.3^n）。只在不大的 n 上可行。
這些仍是「指數」的——更小的底數（2 降到 1.3）並不會讓問題變多項式；它只是把可行的 n 延長一個常數倍。降低底數往往付出沉重的記憶體（Held-Karp 用 2^n 空間）或大的多項式因子，所以實際好處是真的，但有限。