多項式時間近似方案（polynomial-time approximation scheme, PTAS）
固定的近似比（頂點覆蓋的 2、集合覆蓋的 ln n）給你的就是演算法剛好交出的那個精度——要不要隨你。有些問題比較友善：它們讓你「調出」你想要的精度。多項式時間近似方案是一個帶旋鈕 epsilon 的單一演算法，你把旋鈕設成任何小正值，它就承諾給出一個在最佳值 (1 + epsilon) 因子之內的解——你要多接近完美就多接近——而且在輸入規模 n 上仍以多項式時間執行。
仔細讀這個定義，因為精度的代價藏在執行時間裡。一個 PTAS 同時吃進實例和你選的 epsilon，而對「每個固定的」epsilon，它以 n 的多項式時間執行。關鍵的微妙之處是：對 epsilon 的依賴可能極其可怕——執行時間被允許隨 epsilon 縮小而爆炸，像 O(n^(1/epsilon)) 或 O(2^(1/epsilon) * n) 那樣。所以要求 epsilon = 0.5（50% 以內）也許很快，但 epsilon = 0.01（1% 以內）可能慢到天文數字，因為 1/epsilon 現在坐在指數上。承諾只是：一旦你定下某個特定的 epsilon，對 n 的依賴是多項式；而附在那個多項式上的常數與指數，可以是 1/epsilon 的龐大函數。典型的 PTAS 靠利用結構運作：對某些幾何與排程問題，你可以把實例切成夠小的塊，用暴力法或動態規劃近最佳地解出，塊的大小由 epsilon 掌控。
為何這個區別重要：PTAS 是一個強陳述——它說問題能在多項式時間內被任意逼近，所以不存在固定的不可近似屏障。那比頂點覆蓋（卡在常數）或集合覆蓋（卡在 log n）明顯是更好的處境。但「對每個 epsilon 是多項式」是個沒聽起來那麼強的承諾；若執行時間是 n^(1/epsilon)，這個方案對你真正想要的高精度而言並不實用。修正這點的更強、更實用的表親——讓執行時間對 1/epsilon 也是多項式——就是 FPTAS。
假設某問題的一個 PTAS 以 O(n^(1/epsilon)) 時間執行。對 epsilon = 1/2 它是 O(n^2)——還好。對 epsilon = 1/10（10% 以內）它是 O(n^10)——已經很痛。對 epsilon = 1/100 它是 O(n^100)——實務上無用。這個方案對每個固定 epsilon 確實是多項式，但你要求越高精度，指數就越爆炸。
PTAS 對每個固定 epsilon 是 n 的多項式，但對 1/epsilon 可能是指數。
PTAS 中的「多項式」指的是對每個「固定」epsilon 而言對 n 是多項式——對 1/epsilon 的依賴不受限制，常常是指數，例如 n^(1/epsilon)。所以 PTAS 在你真正想要的高精度上可能慢得無望；FPTAS 是修正這點的版本。