完全多項式時間近似方案（fully polynomial-time approximation scheme, FPTAS）
PTAS 讓你調精度，但你要求越多，它的執行時間可能爆炸——像 n^(1/epsilon) 那樣，epsilon 一小就無用。完全多項式時間近似方案是移除這個陷阱的黃金標準：它是一個 (1 + epsilon) 近似方案，其執行時間對輸入規模 n「以及」1/epsilon「兩者」都是多項式。收緊精度，成本只會優雅地成長，像 1/epsilon 的多項式，而非爆炸。
精確的要求就在「完全」這個詞。PTAS 是對每個固定 epsilon 對 n 多項式，對執行時間如何糟糕地依賴 epsilon 沒有限制。FPTAS 把它升級：執行時間必須對 n 和 1/epsilon「一起」是多項式，例如 O(n^2 / epsilon) 或 O(n^3 / epsilon)。現在把 epsilon 減半（1/epsilon 加倍）只把執行時間乘上一個近乎常數的因子，所以高精度真正負擔得起。建造 FPTAS 的教科書辦法是對一個動態規劃做「捨入與縮放」：取一個執行時間依賴輸入數字大小的精確 DP（一個偽多項式演算法），然後刻意把那些數字往下捨到較少的有效位數——粗到讓 DP 變快，細到讓損失的精度最多花掉最佳值的 epsilon 分。所選的縮放把位數的粗細直接綁到 epsilon。
為何 FPTAS 坐在階層的頂端：它基本上是在沒有多項式精確演算法之下你能盼到的最佳——任意精度，而代價對 n 和 1/epsilon 兩者都只是溫和的多項式。背包與子集合加總是著名的例子。誠實的邊界：不是每個問題都有。一個標準結果說：除非 P = NP，強 NP 困難問題不可能有 FPTAS，這正是為何 FPTAS 出現在像背包這種基於數字的問題（其難度來自大數字），卻「不」出現在像一般 TSP 或最大團這種即使數字很小也很難的問題上。所以 FPTAS 在存在時是個美妙的結果，但它的存在本身就是一個強而問題專屬的事實。
背包的 FPTAS 以 O(n^2 / epsilon)（或類似）時間執行：n 和 1/epsilon 都只以多項式出現。要求 1% 精度（epsilon = 0.01）的代價是 1/epsilon = 100 這個因子——一個常數乘子，不是爆炸的指數。對比一個 PTAS 在同樣精度下的 n^(1/epsilon) = n^100。
對 n「以及」1/epsilon 都是多項式：收緊精度仍然便宜。是最強的方案。
強 NP 困難問題除非 P = NP 否則沒有 FPTAS。所以 FPTAS 存在於像背包這種數字問題（只因大數字而難），卻不存在於像一般 TSP 或團這種即使數字很小也仍難的問題。存在性是一個強而問題專屬的事實。