如果我们能证明容量有限的背包问题在多项式时间内得到解决那么所有的背包都属于P
If we can prove that knapsack problem with limited capacity are solved in a polynomial time then all knapsack belongs to P
我在我的优化算法课程中发现了这个问题，完整的问题是这样的：
如果我们能证明所有容量限制为100的背包问题都可以在多项式时间内解决，那么所有的背包问题都属于P。这句话是对还是错？对齐。
根据我的书和一些研究，我得出了这样的结论：
首先，KP 是一个 NP 完全问题。使用动态规划，它可以达到伪多项式时间，但这还不够。
如果，荒谬的是，我们可以证明容量限制为 100 的 KP 可以在多项式时间内求解，那么我们可以假设 KP 属于 P.
你觉得我的回答怎么样？我觉得最后一句荒谬的不太对。
证明所有容量有限的背包问题都可以在多项式时间内解决，并不能证明所有背包问题都在P中。如果一个问题在P中，那就意味着它可以在多项式时间内解决。这意味着它可以在 O(n^k) 中解决，其中 k 是某个整数。 Big O 是一个上限，这意味着，如果一个算法是 O(n)，当 n 接近无穷大时，执行算法所花费的时间永远不会超过 n。通过证明 n<100 的所有问题都可以在多项式时间内解决，这并不能保证 n 更大。因此我们不能说有一个算法在 O(n^k) 中运行，因此在 P.
我在我的优化算法课程中发现了这个问题，完整的问题是这样的： 如果我们能证明所有容量限制为100的背包问题都可以在多项式时间内解决，那么所有的背包问题都属于P。这句话是对还是错？对齐。
根据我的书和一些研究，我得出了这样的结论： 首先，KP 是一个 NP 完全问题。使用动态规划，它可以达到伪多项式时间，但这还不够。 如果，荒谬的是，我们可以证明容量限制为 100 的 KP 可以在多项式时间内求解，那么我们可以假设 KP 属于 P.
你觉得我的回答怎么样？我觉得最后一句荒谬的不太对。
证明所有容量有限的背包问题都可以在多项式时间内解决，并不能证明所有背包问题都在P中。如果一个问题在P中，那就意味着它可以在多项式时间内解决。这意味着它可以在 O(n^k) 中解决，其中 k 是某个整数。 Big O 是一个上限，这意味着，如果一个算法是 O(n)，当 n 接近无穷大时，执行算法所花费的时间永远不会超过 n。通过证明 n<100 的所有问题都可以在多项式时间内解决，这并不能保证 n 更大。因此我们不能说有一个算法在 O(n^k) 中运行，因此在 P.