背包问题：P!=NP下不存在多项式时间绝对近似算法

当P!=NP时，背包问题没有多项式时间绝对近似算法。这是因为，如果存在一个多项式时间绝对近似算法，那么我们可以用它来解决NP完全问题，而这是不可能的，因为NP完全问题是没有多项式时间算法的。因此，我们可以得出结论，当P!=NP时，背包问题没有多项式时间绝对近似算法。

原文地址: https://www.cveoy.top/t/topic/oHde 著作权归作者所有。请勿转载和采集!