询问完全多项式时间近似方案是否属于多项式时间近似方案及相关判断题

判断题1：对于任意固定的ε>0，运行时间为O(n^ε/ε)的近似方案是完全多项式时间近似方案。 #

答案：错误

拆解一下原因：FPTAS要求运行时间是n和1/ε的二元多项式，也就是n的指数是固定常数，1/ε的指数也是固定常数，不能随ε变化。但这里的时间复杂度是O(n^ε/ε)——n的指数是ε本身，当ε变化时（比如ε取0.1、0.01），这个指数也跟着变，根本不是固定的常数，完全不满足FPTAS的要求。

甚至往深了说，这个方案连PTAS都算不上：PTAS要求固定ε时运行时间是n的多项式，而多项式的指数必须是非负整数，n^ε当ε不是整数时（比如ε=0.5），本质是n的根号，不属于标准的多项式范畴。

判断题2：对于任意固定的ε>0，运行时间为O(n²(1/ε)³)的近似方案是多项式时间近似方案。 #

答案：正确

PTAS的核心门槛就是“固定ε时，运行时间是n的多项式”。这里当ε固定时，(1/ε)³是个确定的常数，所以整体运行时间就是O(n²)，这是n的二次多项式，完美符合PTAS的定义。而且这个方案其实还是FPTAS（因为时间是n和1/ε的二元多项式），自然也属于PTAS的范畴。

内容的提问来源于stack exchange，提问作者Feng Hang