多項式時間近似スキーム
ナップサック問題はFPTASがある問題の例である.
多項式的に有界な目的関数を持つどんな強度にNP困難な最適化問題も、P=NPでない限り、FPTASを持ち得ない。 しかし、逆は真ではない。例えば、P≠NPのとき、2つの制約をもつナップサック問題はFPTASを持たないが、たとえ目的関数が多項式的に有界の場合でも強度にNP困難ではない。
P=NPでない限り、 F P T A S ⊊ P T A S ⊊ A P X {\displaystyle FPTAS\subsetneq PTAS\subsetneq APX} が成り立つ。すなわち、同じ仮定の下で、APX困難な問題はPTASを持たない。
別の決定論的なPTASの変形として、準多項式時間近似スキーム(QPTAS)がある。QPTASはある固定された ε {\displaystyle \varepsilon } に対して n p o l y l o g ( n ) {\displaystyle n^{polylog(n)}} の時間複雑度を持つ。