什么是NPC(Nondeterministic polynomial complete)问题？
NPC问题的定义：
如果一个语言B属于NPC问题，那么其满足以下两个条件：
1、B属于NP问题
2、任何属于NP问题的语言A都可以多项式时间规约到B
NPC问题为证明P问题与NP问题等价提供了一个很好的思路，即：假设一个问题B属于NPC问题，并且B属于P问题（这与NPC定义中，B属于NP问题并不矛盾，B属于NP问题当且仅当有一个非确定性图灵机在多项式时间内可以判定B，显然P问题是NP问题的子集），那么任何属于NP问题的语言都可以多项式规约到B，也即是说，P=NP。
什么是子集求和问题？
子集求和问题（SUBSET-SUM）可以形式化定义为：
SUBSET-SUM = { <s,t> | s = {x1,x2,...,xk}, ∃ {y1,y2,...,yl} ⊆ {x1,x2,...,xk} s.t. ∑ yi = t }
e.g. 给出{<2,5,10,19>,15}，其属于SUBSET-SUM问题。
可以证明，子集求和问题属于NP问题，证明方法有两种：1、给出一个多项式时间内的子集求和问题的验证机；2、给出可以在多项式时间内判定子集求和问题的非确定性图灵机。此处不展开讨论。
如何证明子集求和问题是NPC问题？
如果一个语言A属于NPC问题，语言B属于NP问题，并且如果语言A多项式时间可规约到语言B，那么语言B也属于NPC问题。（根据NPC问题的定义可以证明）
因此，我们证明子集求和问题是NPC问题的思路是：找到一个NPC问题，并且证明该NPC问题可以规约到子集求和问题上。
在这里，我们选择的NPC问题是3SAT问题。
1. SAT问题与3SAT问题
3SAT问题很容易去描述，我们先来说什么是SAT问题。
SAT（Satisfiability Problem）问题即是一类判定一个布尔公式是否可满足的问题，其形式化定义为：
SAT = { <𝜙> | 𝜙 is a satisfiable boolean formula }
举个例子，有布尔表达式𝜙 = ( !x ∧ y ) ∨ ( x ∧ !y )，则𝜙 ∈ SAT。（由于公式排版太复杂的原因，用!x代替，后文同样如此）
而3SAT问题就是SAT问题的一种特殊情况。我们规定，一个文字是一个布尔变量或布尔变量的非，如x或!x。一个子句是由∨连接若干文字组成的，如( x1 ∨ x2 ∨ !x3 ∨x4)。一个布尔公式若是由∧连接若干子句组成的，将其称为合取范式或cnf公式，如：
( x1 ∨ x2 ∨ !x3 ∨x4) ∧ ( x1 ∨ x2 ) ∧ ( x1 ∨ x5 ∨ !x6 )
那么，如果一个cnf公式的每个子句都只包含3个文字，就称其为3cnf公式，如：
( x1 ∨ x2 ∨ x3 ) ∧ ( x3 ∨ x5 ∨x6 ) ∧ ( !x1 ∨ x2 ∨ !x4 ) ∧ ( !x2 ∨ x3 ∨ !x4 )
SAT问题与3SAT问题都是NPC问题，可以通过库克-列文定理（Cook-Levin）证明。
2. 把3SAT问题规约到SUBSET-SUM问题
我们证明该命题的整体思路是：找到一个多项式时间的规约方法𝒇，使得如果有𝓌∈3SAT，那么就有𝒇(𝓌)∈SUBSET-SUM，同时，如果有𝒇(𝓌)∈SUBSET-SUM，那么也必须有𝓌∈3SAT。
给定一个布尔表达式𝜙∈3cnf，其存在n个变量以及m个子句，我们假设其变量分别为x1,x2,...,xn，其子句分别为c1,c2,...,cm。
对于这个布尔表达式𝜙，我们可以找到一个与𝜙相符合的子集求和问题，将该子集求和问题描述为(<S>,t)。那么，集合S中一共包含2n+2m个元素，这其中包含了：对于每一个xi∈{x1,x2,...,xn}，有与之对应的vi与v'i；对于每一个ci∈{c1,c2,...,cm}，有与之对应的si与s'i，因此S={v1,v'1,v2,v'2,...,vn,v'2,s1,s'1,s2,s'2,...,sm,s'm}。同时，S中的每一个元素由n+m位组成，t也由n+m位组成。需要注意的是，对于每一个在S中的元素以及t，他们都是由十进制表示的数字。例如，t由5位组成，这5位从左到右分别是1，2，3，4，5，那么t就等于12345。
我们构造一张规约表，该表有2n+2m+1行，n+m列。其中，前2n行代表了集合S中的v1,v'1,v2,v'2,...,vn,v'n。之后的2m行代表了集合S中的s1,s'1,s2,s'2,...,sm,s'm。第2n+2m+1行代表t。前n列代表了𝜙中的n个变量，后m列代表𝜙中的m个子句。其大概规模是这样的：
对于布尔表达式𝜙，我们依照下面的规则构造该规约表：在前2n行中，vi以及v'i的第i列设为1，如果文字xi出现在子句cj中，则设置行为vi中列为cj的位为1，如果文字!xi出现在子句cj中，则设置行为v'i中列为cj的位为1，除了这三种情况外，其余位全设为0。在之后的2m行中，设行为si中列为ci的位为1，设行为s'i中列为ci的位为2，其余位设0。在第2n+2m+1行，设前n列位1，后m列为4。
以上表述你肯定看不懂，我举个例子你就懂了，其实很简单。
假设𝜙 = ( x1 ∨ x2 ∨ !x3 ) ∧ ( !x1 ∨ x2 ∨ x3 ) ∧ ( !x1 ∨ !x2 ∨ x3 ) ∧ ( x1 ∨ !x2 ∨ x3 )，则有如下的规约表：
该规约表实际上给出了SUBSET-SUM问题的构造(<S>,t)，其中<S>={1001001,1000110,0101100,0100011,...,0000002}，t=1114444。所以我们说，对于一个给定的布尔表达式𝜙，实际上我们必须找到这样的一个子集求和问题，使得他们之间可以进行规约。
给出一个布尔表达式𝜙构造这张表是容易的，但是如何说明这张表是一个从3SAT问题到SUBSET-SUM问题的一个多项式时间规约方法呢？我们需要从两个方向进行论证。
1、给定一组{x1,x2,...,xn}的赋值，如果𝜙满足这组赋值，那么存在一个集合S'⊆S，其和为t。
我们说，如果xi的赋值为1，那么便取行vi，如果xi的赋值为0，那么便取行v'1。我们选的这n行中，前n列中的每一列的和必然为1，因为对于某一个变量xi，其取值要么为1要么为0，后m列中，每一列的的和必然为1～3，因为对于布尔表达式3cnf的每一个子句，至少有一个文字必须为真，最多三个文字全为真。需要注意的是，我们选择的每一行，实际上都是在从集合S中选择元素。
为了让后m列中的每一列的和为4，我们需要合理地选取之后的2m行，我们说，如果列cj在当前n个元素的选择下的和为1，那么我们就选上sj与s'j，从而使得这一列的和为1+1+2=4（如上图中，C1,S1,S'1的情况所示）。如果列cj在当前n个元素的选择下的和为2，那么我们就选上s'j，从而使得这一列的和为2+2=4（如上图中的C3,S'3所示）。如果列cj在当前n个元素的选择下的和为3，那么我们就选上sj，从而使得这一列的和为3+1=4（如上图中的C4,S4所示）。
这样一来，就保证了我们所选取的所有行（S的子集中的元素），其每一列的和必然等于t的每一列的值。也即是说，给定满足𝜙的一组赋值，存在一个子集S'使其和为t。
2、如果存在一个集合S'⊆S，其和为t，那么存在一组{x1,x2,...,xn}的赋值，使得𝜙满足这组赋值
我们知道，对于子集S'，对于i=1～n，其必然包含了vi或者v'i（因为行为t的前n列（变量）为1，但是只有vi与v'i的前n列包含1）。那么如果vi在S'中，我们就取xi为真，如果v'i在S‘中，我们就取xi为假。在这种赋值的选取下，我们证明𝜙的每个子句必然都成立。
由于我们选取的子集S‘中的行（元素）的后m列（子句）中，每一列的和为4，但是s与s'的每一列的和最大为3，所以必然会选取某个v或者v'，使得v或者v'在该列的值为1，那么这样就表示在该子句中，存在相应的一个文字。具体来说，如果选取了vi，就表示该子句中存在xi，并且由于我们取xi为真，因此该子句为真；如果选取了v'i，就表示该该子句中存在!xi，并且我们取xi为假，因此该子句为真。
这样一来，就说明了给定一个和为t的集合S'，存在一组满足𝜙的赋值。
综上所述，我们证明了3SAT问题可以多项式时间规约到SUBSET-SUM问题，从而证明了SUBSET-SUM属于NPC问题。
参考资料
Proof of NP-Completeness of the Subset Sum Language
The NP-completeness of Subset Sum
Introduction to the Theory of Computation - 3rd edition
Reduction : 3-CNF SAT to Subset Sum
心得体会
一开始思考这一题，完全只参考了《计算理论导引》这一本教材，但是这本教材对这个问题的证明过程描述十分粗略，大量的推导所需要的信息（如每一行每一列表示了什么，该如何在规约表中表示一个子集求和过程...）都没有告诉读者就开始证明，这一度让我十分苦恼。之后在网络上查找对该问题的不同版本的证明，渐渐地补全了推导所必要的每条信息。有意思的是，我看到的每一个不同版本的证明，他们基本上都不完全相同。所以说，广泛查阅资料搜寻有用的信息是十分重要的。
