我知道我们可以将 FPTAS 应用于像 0-1 背包这样的弱 NP 问题。
但是为什么我们不能将相同的原则应用于像装箱这样的强 NP 问题。我也检查了 wiki 页面，但理解得很少。
问问题
331 次
1 回答
2
如果一个严格的 NP 完全问题具有 FPTAS，您可以“欺骗”近似算法以提供最佳解决方案。详情在这里：http ://www.idi.ntnu.no/~mlh/algkon/complexity.pdf
该 FPTAS 的存在将为 NP 完全问题提供多项式时间算法。
于 2013-11-01T17:50:11.700 回答