集合划分问题的 NP 完备性证明
Proof of NP Completeness of set-partition problem
我已经将子集和问题归约到设置分区问题，但不知道是否正确，所以我需要你的帮助。
我的方法：
在子集求和问题中，我们必须找到集合 S 的子集 S1，以便它总和为数字 t；在集合划分问题中，我们需要找到集合 X 的子集 X1，这样集合 X1 中数字的总和是集合 X1 中数字总和的一半X。
因此，让我们以子集和问题为例，其中 t = X / 2 中的数字总和。如果我们能够解决集合划分问题，那么我们也解决了子集和问题。但是我们知道子集和 id NP Complete 所以子集和问题也是 NP Complete（我知道如何证明它是 NP）。
我怀疑我们是否可以这样选择 t。请帮忙。
你的逻辑很合理，这是一个有效的归约。
我们知道这是有效的，因为证明是针对已知问题到未知问题。您需要证明已知问题的每个实例都可以简化为未知问题的某些实例。因此，对您的未知问题施加限制是完全可以接受的。
一些注意事项：您的描述不足以作为适当的证明。你注意到你知道这一点，但对于这里的任何读者来说：要证明一个问题是 NP-Complete，你首先要证明它是 NP，然后你证明它是 NP-Hard。这个问题只解决了 NP-Hard 证明应该包含的一小部分内容。
我已经将子集和问题归约到设置分区问题，但不知道是否正确，所以我需要你的帮助。
我的方法：
在子集求和问题中，我们必须找到集合 S 的子集 S1，以便它总和为数字 t；在集合划分问题中，我们需要找到集合 X 的子集 X1，这样集合 X1 中数字的总和是集合 X1 中数字总和的一半X。
因此，让我们以子集和问题为例，其中 t = X / 2 中的数字总和。如果我们能够解决集合划分问题，那么我们也解决了子集和问题。但是我们知道子集和 id NP Complete 所以子集和问题也是 NP Complete（我知道如何证明它是 NP）。
我怀疑我们是否可以这样选择 t。请帮忙。
你的逻辑很合理，这是一个有效的归约。
我们知道这是有效的，因为证明是针对已知问题到未知问题。您需要证明已知问题的每个实例都可以简化为未知问题的某些实例。因此，对您的未知问题施加限制是完全可以接受的。
一些注意事项：您的描述不足以作为适当的证明。你注意到你知道这一点，但对于这里的任何读者来说：要证明一个问题是 NP-Complete，你首先要证明它是 NP，然后你证明它是 NP-Hard。这个问题只解决了 NP-Hard 证明应该包含的一小部分内容。