algorithm - 如何在多项式时间内设置分区？

Question

我刚刚阅读了有关在多项式时间内将设置分区解决为一半的可能性。但我找不到算法来做到这一点。

我有两个问题：

1. 我在哪里可以得到那个算法？
2. NP问题怎么可能在多项式时间内解决？

Answer 1

你应该提到你在哪里读到的。您可能偶然发现了多项式逼近算法或伪多项式精确算法（存在动态规划伪多项式解决方案），但绝对不是多项式精确算法 - 因为分区问题是 NP 问题，并且没有多项式算法可以解决它，除非P=NP。

Answer 2

你不能，它是 NP 完全的，到目前为止还没有办法在 P 时间内解决一个 NP 完全问题。