我了解到分区问题已包含在NP-Hard问题中。我已经对该问题进行了一些搜索，但似乎找不到用于某个特定问题的原因，对于特定算法无法得出结论，P = NP。
如果可以在时间𝑂（𝑛𝑀）中解决分区问题，其中𝑛是集合中元素的数量，而𝑀是集合中元素的绝对值之和。为什么基于这些，不能得出P = NP的结论？
P和NP的定义表明存在一种在多项式时间内运行的算法（在NP的情况下是不确定的）。诀窍是多项式的参数是问题的size，其定义为对问题实例进行编码的位数。
分区问题的诀窍在于，数字在编码它们的位数方面是指数的，所以so（𝑛𝑀）在编码大小方面实际上是指数的。
存在确定性多项式时间算法且其中多项式的自变量是定义问题的数字的NP-完全问题的类别称为弱 NP-完全。隔板，背包和类似物品属于此类。
相关的维基百科条目：https://en.wikipedia.org/wiki/Weak_NP-completeness
因为M是元素的绝对值之和。它不是n的多项式，因此不是多项式时间算法。对于背包问题，采用动态编程解决方案的想法相同。