如何在多项式时间内进行集合划分？
我刚刚读到有关在多项式时间内解决集分区一半的可能性。但我找不到算法来做到这一点。
我有两个问题：
- 我在哪里可以获得该算法？
- NP问题怎么可能在多项式时间内解决呢？
I've just read about possibility to solve set partition to half in polynomial time. But I could not find algorithm to do it.
I have two questions:
- Where I can get that algorithm?
- How is it possible that NP problem can be solved in polynomial time?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您应该提及您到底在哪里读到的。您可能偶然发现了多项式近似算法，或伪多项式精确算法（动态规划伪多项式解决方案存在），但绝对不是一个多项式的精确算法 - 因为分区问题是一个 NP 问题，并且没有多项式算法可以解决它，除非P=NP。
You should mention where exactly did you read that. It's possible that you stumbled upon a polynomial approximation algorithm, or a pseudo-polynomial exact algorithm (a dynamic programming pseudo-polynomial solution exists), but definitely not a polynomial, exact algorithm - since the partition problem is an NP problem, and no polynomial algorithm can solve it, unless P=NP.
你不能，它是 NP 完全问题，到目前为止还没有办法在 P 时间内解决 NP 完全问题。
You cannot, it's NP-complete and thus far there is no way to solve an NP-complete problem in P time.