3-partition问题为何是NP完全？求Partition到它的归约示例

一、你混淆了两个完全不同的问题 #

你提到的O(n³)解法对应的是三数之和问题——只需要在集合里找到任意一个和为目标值的三元组就行，这个问题确实是多项式时间可解的（甚至能优化到O(n²)）。

但3-partition问题的定义完全不一样：给定一个包含3k个正整数的集合，每个元素的大小严格在「单个三元组目标和的1/4到1/2」之间，要判断能不能把整个集合全部分割成k个不相交的三元组，每个组的和都等于目标值（也就是集合总和除以k）。

核心差异：

• 3-partition要求所有元素都必须被用到，且刚好分成k个三元组，不是找一个就算完。
• 元素大小的限制是关键：它保证了单个元素、两个元素都凑不出目标和，只能用三个元素，这让问题的复杂度直接上升到NP完全级别。

二、为什么3-partition是NP完全问题 #

要判定一个问题是NP完全，需要满足两个条件：

1. 属于NP类：给一个候选解（已经分好的k个三元组），我们能在多项式时间内验证每个组的和是否相等，且所有元素都被使用——这显然是可行的，遍历一遍就行。
2. NP难：可以从一个已知的NP完全问题（比如Partition问题）归约到它，证明它至少和所有NP问题一样难。

三、从Partition到3-partition的归约示例 #

先明确两个问题的定义 #

• Partition问题：给一个正整数集合，判断能不能把它分成两个不相交的子集，两个子集的和完全相等。
• 3-partition问题：如前所述，把3k个元素分成k个和相等的三元组，每个元素满足大小限制。

归约步骤（用具体例子说明） #

假设我们有一个Partition问题的实例：集合A={3,3}，总和是6，显然能分成两个子集{3}和{3}，和都是3。

现在我们构造一个对应的3-partition问题实例：

1. 确定k值：因为A有2个元素，我们让3-partition的k=2，也就是需要6个元素。
2. 设定目标和T：选T=10（满足后续元素大小在T/4=2.5到T/2=5之间）。
3. 构造集合S：
   • 对A中的每个元素3，生成两个元素：3和3（都在2.5到5之间）。
   • 添加2个元素4，再添加2个元素3（同样符合大小要求）。
   • 最终S={3,3,3,3,4,4}，总和是20，刚好分成2个三元组，每个目标和10。
4. 对应关系：
   • Partition的解是两个{3}，对应3-partition的两个三元组{3,3,4}和{3,3,4}，每个组的和都是10，且所有元素都被用到。
   • 反过来，如果这个3-partition问题有解，那每个三元组必然是两个3加一个4，我们可以把每个三元组中的一个3拿出来，组成两个子集{3}和{3}，刚好是Partition问题的解。

严谨归约逻辑（通用版） #

对于任意Partition问题实例（集合A总和为2S），我们构造3-partition实例：

• 取k=|A|，构造3k个元素：
  1. 对每个a∈A，生成两个元素：a和(S - a + M)，其中M是一个足够大的数，确保所有元素都在T/4到T/2之间（T是3-partition的目标和，设为2S + 2M）。
  2. 添加k个元素M。
• 此时3-partition的目标和T=(Σ(a + (S-a+M)) + k*M)/k=(Σ(S+M)+kM)/k=(k(S+M)+kM)/k=S+2M。
• 验证元素大小：每个元素a<S+2M/2=S+M，且a> (S+2M)/4（只要M足够大就能满足）；S-a+M> (S+2M)/4，且<S+M；M也满足大小要求。
• 当Partition有解时，我们可以将每个a∈子集X（和为S）与对应的(S-a+M)、M组成三元组，和为a+(S-a+M)+M=S+2M=T；同理处理子集Y，刚好得到k个三元组。反之，3-partition的解也能直接导出Partition的解。

参考内容翻译 #

3-partition问题原定义 #

3-partition问题是强NP完全的组合优化问题，定义为：给定包含3k个正整数的集合S，以及每个三元组的目标和T（等于S的总和除以k），其中每个元素的值严格在T/4到T/2之间，判断是否能将S划分为k个不相交的三元组，使得每个三元组的元素之和等于T。

三数之和问题解决方案 #

三数之和问题的目标是在给定整数数组中找到所有不重复的三元组，使其和等于给定目标值。常见解法包括：

• 暴力法：三重循环遍历所有可能的三元组，时间复杂度O(n³)，空间复杂度O(1)（不计结果存储）。
• 哈希表法：固定一个元素，用哈希表寻找另外两个元素的和等于目标值减去该元素，时间复杂度O(n²)，空间复杂度O(n)。
• 双指针法：先排序数组，固定一个元素后用左右指针在剩余元素中寻找和为目标值的对，时间复杂度O(n²)，空间复杂度O(logn)（排序所需空间）。

内容的提问来源于stack exchange，提问作者user