什么是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
心得体会
一开始思考这一题,完全只参考了《计算理论导引》这一本教材,但是这本教材对这个问题的证明过程描述十分粗略,大量的推导所需要的信息(如每一行每一列表示了什么,该如何在规约表中表示一个子集求和过程...)都没有告诉读者就开始证明,这一度让我十分苦恼。之后在网络上查找对该问题的不同版本的证明,渐渐地补全了推导所必要的每条信息。有意思的是,我看到的每一个不同版本的证明,他们基本上都不完全相同。所以说,广泛查阅资料搜寻有用的信息是十分重要的。