我在优化算法课程中发现了这个问题，完整的问题是这样的：如果我们能证明所有容量限制为 100 的背包问题都可以在多项式时间内求解，那么所有背包问题都属于 P。这句话是真是假？辩护。
通过我的书和一些研究，我得出了这样的东西：首先，KP是一个NP完全问题。使用动态编程，它可以达到伪多项式时间，但这还不够。如果荒谬地，我们可以证明容量限制为 100 的 KP 可以在多项式时间内求解，那么我们可以假设 KP 属于 P。
你怎么看我的回答？我认为最后一句话的荒谬并不那么正确。
证明所有容量有限的背包问题都可以在多项式时间内求解，并不能证明所有背包问题都在 P 中。如果一个问题在P中，这意味着它可以在多项式时间内解决。这意味着它可以在 O（n^k） 中求解，其中 k 是某个整数。大 O 是一个上限，这意味着，如果一个算法是 O（n），当 n 接近无穷大时，执行算法所需的时间永远不会超过 n。通过证明 n<100 的所有问题都可以在多项式时间内解决，这并不能保证更大的 n。因此，我们不能说有一种算法在 O（n^k） 中运行，因此在 P 中运行。