我想知道一个近似方案，这是一个完全多项式时间近似方案，它也是一个多项式时间近似方案吗？
例如，在O（N2（1 /ε）3）中运行的近似方案-我们知道它是一个完全多项式时间近似方案。
它也是一个多项式时间近似方案吗？谢谢！
以下是两个相关问题（正确或错误）：
对于任何固定的＞0，在O（n＝2／ω）中运行的一个近似方案是A
完全多项式时间近似方案。
在任何固定＞0的O（n2（1／ε）3）中运行的一个近似方案
多项式时间近似方案。
最佳答案
谢谢你提这个有趣的问题我做了一个小的研究，并在PTAS（多项式时间近似方案）和完全PTAS上提出了这个“AA>”。
如讲座所述：
算法的运行时间应为n的多项式；
但是，对ε的依赖性可以是指数的。所以运行时间可以是
例如O（（2^（1/ε））*n^2），或O（n^（1/ε）），或O（（n^2/ε）等，如果
对参数1/ε的依赖也是多项式的，然后我们说
完全多项式时间近似方案（FPTAS）。在这次讲座中我们
举一个fptas的例子。
由于ptas中ε的需求是指数依赖的，那么cleary fptas是ptas的一个子情况，因为1/ε是多项式依赖的（o（fptas）底线-FPTA是PTA。