判断题
多项式时间近似方案的时间复杂度是P(n,1/q),P是多项式函数,q〉0。
错误(↓↓↓ 点击‘点击查看答案’看答案解析 ↓↓↓)
判断题 多项式时间近似方案的近似性能比是1+q,q〉0。
判断题 最大优化问题的近似性能比小于1,越接近1越说明算法好。
判断题 若P不等于NP,则最大独立集问题存在多项式时间绝对近似算法。