从 PARTITION 到 SUBSET SUM 的 Karp 缩减
Karp reduction from PARTITION to SUBSET SUM
分区：给定一组正整数 A={a_1,...,a_n} 是否存在 A 的子集其和等于其补码之和？
SUBSET SUM：给定一组正整数 A={a_1,...,a_n} 和另一个正整数 B，是否存在 A 的子集使得它的和等于 B?
我试图通过将 PART 简化为 SSUM 来证明如果 PARTITION 是 NP 完全的，那么 SUBSET SUM 也是 NP 完全的。
我的解决方案是：设 A={a1,...,an} 为一组正整数。然后，如果将 A 输入 PART 时给出解 I={k1,...,km}（其中 k_i 是解子集成员的索引），那么我们构造 A'={a1,. ..an,S} 其中 S 是 {a_k1,a_k2,...,a_km} 的总和。 A' 是 SSUM 的解决方案。
我的问题是这只有一种方式，这意味着我们无法证明给定 A' 那么 A 是 PART 的解。这是个问题吗？我该如何修改证明以涵盖它？
分区到 SubsetSum 实际上比您在此处所做的更容易。
如果满足分区，则意味着存在一些子集 P1 和 P2，使得 sum(P1) = sum(P2) 正确吗？因为sum(P1) + sum(P2) = Sum(A)，也就是说sum(P1) = sum(P2) = (1/2)sum(A)
我们甚至不需要为子集和构建 A'。只需设置 A' = A 和目标总和 = (1/2)sum(A)。应该清楚，这与几乎没有抽象的分区完全相同。
换句话说，分区总是只是子集总和，其中目标总和 = (1/2)sum(A)
分区：给定一组正整数 A={a_1,...,a_n} 是否存在 A 的子集其和等于其补码之和？
SUBSET SUM：给定一组正整数 A={a_1,...,a_n} 和另一个正整数 B，是否存在 A 的子集使得它的和等于 B?
我试图通过将 PART 简化为 SSUM 来证明如果 PARTITION 是 NP 完全的，那么 SUBSET SUM 也是 NP 完全的。
我的解决方案是：设 A={a1,...,an} 为一组正整数。然后，如果将 A 输入 PART 时给出解 I={k1,...,km}（其中 k_i 是解子集成员的索引），那么我们构造 A'={a1,. ..an,S} 其中 S 是 {a_k1,a_k2,...,a_km} 的总和。 A' 是 SSUM 的解决方案。
我的问题是这只有一种方式，这意味着我们无法证明给定 A' 那么 A 是 PART 的解。这是个问题吗？我该如何修改证明以涵盖它？
分区到 SubsetSum 实际上比您在此处所做的更容易。
如果满足分区，则意味着存在一些子集 P1 和 P2，使得 sum(P1) = sum(P2) 正确吗？因为sum(P1) + sum(P2) = Sum(A)，也就是说sum(P1) = sum(P2) = (1/2)sum(A)
我们甚至不需要为子集和构建 A'。只需设置 A' = A 和目标总和 = (1/2)sum(A)。应该清楚，这与几乎没有抽象的分区完全相同。
换句话说，分区总是只是子集总和，其中目标总和 = (1/2)sum(A)