Zeta Archive: 子集和问题的NPC属性证明：从3SAT到整数集合的多项式时间归约

子集和问题的 NPC 属性证明

背景与定义：计算复杂性理论的核心问题

在计算复杂性理论中，NP 完全问题（NPC）代表了一类特殊的决策问题：它们既是 NP 问题（能在多项式时间内验证解），又能通过多项式时间归约接收所有 NP 问题的实例。1972 年，Karp 证明了 21 个经典问题的 NPC 属性，其中子集和问题（Subset Sum）因其简洁的表述和广泛的应用成为重要成员。子集和问题的形式化定义为：给定正整数集合和目标值，是否存在非空子集使得？

证明子集和问题为 NPC 的标准路径是从 3SAT 问题规约。3SAT 问题要求判定一个 3 合取范式（3 - CNF）公式是否存在可满足赋值，其中每个子句包含 3 个文字（变量或其否定）。由于 3SAT 是已知的 NPC 问题，若能构造多项式时间的映射，将 3SAT 实例转化为子集和实例，且保持解的等价性，则子集和问题的 NPC 属性得证。

规约框架：数字编码与约束构造

归约的核心思想是用整数的二进制位编码逻辑变量的赋值状态，并通过数位约束模拟子句的可满足性。具体分为三个步骤：变量编码、子句约束和填充元素。变量编码是指为每个布尔变量设计两个整数和，通过特定数位确保二者中恰好选择一个，对应变量的真或假赋值。子句约束是指为每个子句分配独立的数位，确保所选变量对应的整数在该数位上的和至少为 1，即子句中存在真文字。填充元素是指通过额外整数修正子句数位的和，使其恰好等于目标值的对应数位，消除冗余解空间。

详细构造：从逻辑变量到整数集合

设 3SAT 实例包含个变量和个子句。构造的子集和实例将包含个整数，目标值为位整数（实际实现中可通过十进制数位分离，避免二进制进位干扰）。

变量数位：确保二选一赋值

变量位设计：将整数的前个数位（称为变量位）分配给变量。对于变量，整数在第个变量位为 1，其余变量位为 0；整数在第个变量位为 1，其余变量位为 0；目标值的前个变量位均为 1。

例如，若，则，，且的前三位为。此时，若从集合中选择恰好一个，则变量位的和恰为，满足目标约束；若选择 0 个或 2 个，则无法满足，从而强制每个变量必须赋值。

子句数位：模拟逻辑析取

子句位设计：将接下来的个数位（称为子句位）分配给子句。对于子句（其中为文字），若（变量为真），则在第个子句位为 1；若（变量为假），则在第个子句位为 1；目标值的第个子句位设为 3（需结合填充元素修正）。

例如，子句对应第 1 个子句位：、、的该位均为 1，其余变量的整数该位为 0。此时，若变量赋值使子句为真，则至少有一个对应整数的子句位为 1，该位的和。

填充元素：修正子句位和为 3

由于子句位的和可能为 1、2 或 3（对应子句中 1、2 或 3 个文字为真），需引入填充元素将其修正为目标值 3。为每个子句添加两个填充整数和，二者在第个子句位均为 1，其他数位为 0；目标值的子句位设为 3，因此（其中为填充元素在第位的和，取值为 0、1 或 2）。

例如，若子句位和，则需选择两个填充元素（）；若，选择一个填充元素（）；若，不选填充元素（）。这确保了只有当子句可满足时（），才能通过填充元素组合使总和等于。

正确性证明：双向等价性验证

正向：3SAT 解导出子集和解

设 3SAT 实例存在满足赋值。构造子集如下：对每个变量，若，选择；否则选择；对每个子句，设为所选变量整数在第子句位的和（），选择个填充元素。

此时，变量位的和为，子句位的和为，总，即是子集和解。

反向：子集和解导出 3SAT 解

设子集和实例存在解。由于变量位的约束，中恰好包含每个变量的一个整数（或），定义赋值当且仅当。对于子句，子句位的和，由于填充元素最多贡献 2（），故，即子句中至少有一个文字为真，是 3SAT 的满足赋值。

复杂度分析：多项式时间的规约映射

编码长度：每个整数的位数为，数值大小为，但编码所需的二进制位数为，是输入规模的多项式函数。

构造时间：生成个整数及目标值的时间为，满足多项式时间要求。

综上，子集和问题可通过多项式时间归约接收 3SAT 实例，且其本身是 NP 问题（验证子集和需时间，其中为集合大小），故子集和问题是 NPC 问题。

结论与扩展：从理论到应用

子集和问题的 NPC 属性揭示了其计算复杂性的本质：不存在多项式时间算法（除非）。这一结论影响深远：在密码学中，基于子集和的背包密码体制（如 Merkle-Hellman）利用了其难解性；在动态规划领域，Bellman 提出的伪多项式算法（其中为目标值）是目前最优的精确解法之一。然而，当呈指数增长时，该算法退化为指数时间，进一步印证了理论上的困难性。