NP完全问题分析

NP 完全问题研究P=NP 的问题有两条基本思路：1．证明NP 类中的某些问题是难解的，从而得到NP ≠P 。

但是要证明这一点几乎同证明P=NP 一样困难。

2．考察NP 类中问题之间的关系，从中找到一些具有特殊性质的、与P 类问题显著不同的问题。

沿着这一路线人们已经证明了在NP 类中存在被称为NP 完全的子类，简称NPC 问题，并由此发展了一套著名的NP 完全理论。

本节简要先介绍NP 完全性理论。

为此，首先给出各语言之间的多项式变换的概念。

定义 1 所谓从一个语言*11∑⊆L 到另一个语言*22∑⊆L 的多项式变换是指满足下面两个条件的函数*2*1:∑→∑f ，(1) 存在计算f 的一个多项式时间DTM 程序；(2) 对于所有的*1∑∈x 有：1L x ∈当且仅当2)(L x f ∈。

用21L L ∝表示存在一个从语言1L 到语言2L 的多项式变换。

相应地，对于判定问题21,∏∏，设e 1和e 2是相应的编码策略。

若],[],[2211e L e L ∏∝∏，则记为21∏∝∏。

也可以从问题的层次来叙述：由判定问题1∏到判定问题2∏的多项式变换是满足下列条件的函数21:∏∏→D D f ，(1) f 可由一个多项式时间的确定性算法来计算；(2) 对于所有的1∏∈I D 有：1∏∈I D 当且仅当2)(∏∈I Y f 。

定义2 称一个语言L （判定问题∏）为NP 完全的（NPC ），如果)(NP NP L ∈∏∈，且对于所有别的语言NP L ∈'（判定问题NP ∈∏'）均有)'('∏∝∏∝L L 。

按照定义2，要证明问题∏是NP 完全的，需要证明所有的NP 问题均能够经多项式变换变成∏。

这几乎是很难做到的。

如果NP 完全问题比较多，我们也不能对每一个这样的问题都这样验证。

为此我们讨论一些NPC 问题的有用的性质。

性质1 如果L L ∝'，则P L ∈意味着P L ∈'。

如何⽤整数规划求解NP完全问题如何⽤整数规划求解NP完全问题⼀、NP完全问题NP完全问题是⼀类具有⾮常⾼难度的组合最优化问题，所有NP完全问题都是NP难问题。

虽然P问题是⽐较容易的问题，NP问题却不⼀定是困难问题，必须看见NP完全或者NP难这样的字才能说这个问题求解起来很困难。

经常听砖家说，NP完全/NP难问题不能⽤整数规划求解。

实际情况怎样？实事证明砖家的话只能信⼀半：）。

这⾥咱就看看⽤整数规划求解⼀个NP完全问题⾏也不⾏。

这⾥有⼀个货真价实的整数规划问题——划分问题（The partition problem）。

问题是：给定⼀个⼤⼩不等的整数集合，问是否可以把这些整数划分成两个集合，任何⼀个整数或者在集合S1中或者在S2中，但不能同时在两个集合中；对任意给的⼀个整数集合，请设计算法，解决是否存在⼀个划分，使得S1种整数之和恰好等于S2集合的整数之和。

⼆、建⽴整数规划模型对每个整数定义⼀个0-1变量xi, xi=1 表⽰第i个整数位于集合S1中， xi=0表⽰第i个整数位于S2中。

⽤s1表⽰第⼀集合的整数之和，⽤s2表⽰第⼆个集合⾥的整数之和。

即：设d是s1和s2之间差的绝对值。

于是：我们只要极⼩化d就可以了，即：完整模型：三、上⾯的模型的⽂本表达上⾯的模型不只是⽤来摆摆看的，还可以真的被求解哈。

我们需要把模型写成⽂本格式（Leapms建模语⾔格式），让计算机理解。

⽬标函数就写成min d加上其余约束部分（注意西格玛符合的写法）subject tos1=sum{i=1,...,n}x[i]S[i]s2=sum{i=1,...,n}((1-x[i])S[i])d>=s1-s2d>=s2-s1加上符号说明（符号必须说明，不然计算机不知道哪些是常数，哪些是变量）wheren is an integerS is a sets1,s2,d are variables of numberx[i] is a variable of binary|i=1,...,n加上数据（注意整数个数是从集合S上⾃⼰数出来的）data_relationn=_$(S)dataS={11,47,159,137,85,47,142,35,119,61,88,175,13,96,-11,176,126,15,98,46,163}四、求解把如下完整模型贴到记事本上，保存为 partition.leap⽂件。

3.4 NP完全性的证明一、六个基本的NPC问题三元可满足性问题(3SAT)三维匹配问题(3DM)顶点覆盖问题（VC）团的问题哈密顿回路(HC)均分问题二、基本NP完全问题的证明三、NP完全问题的证明方法一、六个基本NP完全问题3SAT实例: 有穷布尔变量集U 和U上的子句集C={c1,c2,...,cm},其中|ci|=3, 1≤i≤m.问: 对于U是否存在满足C中所有子句的真值赋值？3DM实例: 集合M ⊆W×X×Y, 其中W,X,Y互不相交, 且|W|=|X|=|Y|=q.问: M是否包含一个匹配, 即是否存在子集M’⊆M使得|M’|= q且M’中任意两个元素的三个坐标都不相同?肯定实例：W={a1,a2,a3,a4},X={b1,b2,b3,b4},Y={c1,c2,c3,c4}M={(a1,b2,c1),(a1,b1,c1),(a2,b1,c2),(a2,b2,c1), (a3,b3,c3),(a4,b4,c4),(a4,b2,c1)}VC实例: 图G=(V,E), 正整数k≤|V|.问: G中是否存在大小不超过k的顶点覆盖, 即是否存在子集V’⊆V,使得|V’|=k, 且对每条边{u,v}∈E都有u∈V’或v∈V’?团实例: 图G=(V,E), 正整数J≤|V|.问: G是否包含大小不小于J的团, 即是否存在子集V’⊆V,使得|V’|≥J, 且V’中每两个顶点都由E中的一条边连接?独立集实例：图G=(V,E)，正整数J≤|V|问：G中是否包含大小不小于J的独立集，即是否存在V’⊆V, 使得|V’|≥J，且∀u,v∈V’，{u,v}∉E?HC实例: 图G=(V,E),|V|=n.问: G 中是否包含一条哈密顿回路, 即是否有G 的顶点排列><n j j j v v v ,...,,21?},{,1,},{11E v v n i E v v j j j i j n i ∈<≤∈+∑=∑-∈∈'')()(A A a A a a S a S 使得均分实例: 有穷集合A, ∀a ∈A 有”大小”S(a)∈Z +问: 是否存在子集A ’⊆ A 使得证明顺序均分HC 团（独立集）1．3SAT∈NPC证明思路证3SAT∈NP将SAT的实例变换成3SAT的实例：根据子句中的文字个数k 分别处理1个子句转变成多个子句保证每个子句含有3个文字转变前与转变后的真值不变证显然3SAT属于NP.设U={u1,u2,...,un}, C={c1,c2,...,cm}是SAT的任何实例.对于C中任意子句c j ={z1,z2,...,zk},构造新增的变量集Uj ’和子句集Cj’.}},,}{,,{},,,{},,,{{'},{'21121121121121j j j j j j j j j j j j y y z y y z y y z y y z C y y U ==C j ’被满足⇔c j 被满足.若k=2, c j ={z 1,z 2}, 则}},,{},,,{{'}{'1211211j j j j j y z z y z z C y U ==C j ’被满足⇔z 1+z 2为真⇔c j 被满足.若k=3, 则U j ’= ∅C j ’= {c j }若k=1, c j ={z 1}, 则},,{},,,{},,,{{'},{'54223112121z z y y z y y z z C y y U j j j j j j j j ==c j 可满足⇔z 1+z 2+...+z 5为真⇒C j ’可满足如z 1+z 2为真, 则y j 1= y j 2 = F ;如z 3为真, 则y j 1= T,y j 2 = F ；如z 4+z 5为真, 则y j 1= T,y j 2 = T .反之, 若C j ’可满足而c j 不满足, 则z 1+z 2+...+z 5为假, 即z 1,z 2,...,z 5全为假, 必须y j 1=T,y j 2 =T, 最后的子句不满足.若k>3, 例如c j = {z 1,z 2,...,z 5}, 则一般若c j ={z 1,z 2,...,z k }, k>3}},,{{}41:},,{{}},,{{'}31:{'1312121k k k ji ji i j j j i j j z z y k i y z y y z z C k i y U --++⋃-≤≤⋃=-≤≤=令U ’= U ⋃U 1’⋃U 2’⋃...⋃U m ’C ’= C 1’⋃C 2’⋃...⋃C m ’下面证明f是多项式变换.易见若t满足C’, 则t满足C. 假若t不满足cj，则z 1,z2,…,zk全为假，只能有Tyyy k jjj====-321...C’的最后一个字句不满足.反之，设t:U→{T,F}是满足C的真值赋值, 将U’－U的变量分成U1’, U2’, ..., Um’, 且Uj’的变量只出现于子句Cj ’中。

NP完全的问题一个NP－完全的问题具有如下性质：它可以在多项式时间内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。

P是所有可在多项式时间内用确定算法求解的判定问题的集合。

NP 问题是所有可用多项式时间算法验证其猜测准确性的问题的集合。

令L1和L2是两个问题，如果有一确定的多项式时间算法求解L1，而这个算法使用了一个在多项式时间内求解L2的确定算法，则称L1约化为L2。

如果可满足性约化为一个问题L，则称L问题是NP-难度的。

如果L是NP难度的且L（－NP，则称L是NP－完全的。

NP并不是NON-POL YNOMIAL，把NP说成是NON-POL YNOMIAL，是望文生义，读书不求甚解。

事实上，如果你能够证明某个NP问题是个NON-POL YNOMIAL的问题，你就可以去领那七个百万美元数学大奖中间的一个了。

数学上著名的NP问题，完整的叫法是NP完全问题，也即“NP COMPLETE”问题，简单的写法，是NP=P？的问题。

问题就在这个问号上，到底是NP等于P，还是NP不等于P。

证明其中之一，便可以拿百万美元大奖。

这个奖还没有人拿到，也就是说，NP 问题到底是Polynomial，还是Non-Polynomial，尚无定论。

NP里面的N，不是Non-Polynomial的N，是Non- Deterministic，P代表Polynomial倒是对的。

NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。

如果一个判定性问题的复杂度是该问题的一个实例规模n的多项式函数，则这种可以在多项式时间内解决的判定性问题属于P类问题。

P类问题就是所有复杂度为多项式时间的问题的集合。

通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题。

有些问题很难找到多项式时间的算法（或许根本不存在），例如“找出无向图中哈米尔顿回路”问题。

但如果给了该问题的一个答案，可以在多项式时间内判断这个答案是否正确。

P问题、NP问题、NP完全问题和NP难问题在讲P类问题之前先介绍两个个概念：多项式，时间复杂度。

(知道这两概念的可以⾃动跳过这部分)1、多项式：axn-bxn-1+c恩....就是长这个样⼦的，叫x最⾼次为n的多项式....咳咳，别嫌我啰嗦。

有些⼈说不定还真忘了啥是多项式了。

例如第⼀次看到的鄙⼈→_→2、时间复杂度我们知道在计算机算法求解问题当中，经常⽤时间复杂度和空间复杂度来表⽰⼀个算法的运⾏效率。

空间复杂度表⽰⼀个算法在计算过程当中要占⽤的内存空间⼤⼩，这⾥暂不讨论。

时间复杂度则表⽰这个算法运⾏得到想要的解所需的计算⼯作量，他探讨的是当输⼊值接近⽆穷时，算法所需⼯作量的变化快慢程度。

举个例⼦：冒泡排序。

在计算机当中，排序问题是最基础的，将输⼊按照⼤⼩或其他规则排好序，有利于后期运⽤数据进⾏其他运算。

冒泡排序就是其中的⼀种排序算法。

假设⼿上现在有n个⽆序的数，利⽤冒泡排序对其进⾏排序，①⾸先⽐较第1个数和第2个数，如果后者>前者，就对调他们的位置，否则不变②接着⽐较第2个数和第3个数，如果后者>前者，就对调他们的位置，否则不变③⼀直向下⽐较直到第n-1和第n个数⽐较完，第⼀轮结束。

（这时候最⼤的数移动到了第n个数的位置）④重复前三步，但是只⽐较到第n-1个数（将第⼆⼤的数移动到第n-1个数位置）⑤持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较。

举个实例：5,4,3,2,1，对其进⾏排序，先是⽐较5跟4变成4,5,3,2,1，第⼀轮结束后变成43215，可以计算，当对其排序完正好要经过4+3+2+1=10次⽐较，当然这是最复杂的情况，即完全反序。

可以知道对于n个数，⾄多要经过1+2+...+n-1即(n^2-n)/2次⽐较才能排好序。

这个式⼦⾥n的最⾼次阶是2，可知道当n→∞时，⼀次性对其⽐较次数影响很⼩，所以我们把这个算法的时间复杂度⽐作：o(n^2)。

取其最⾼次，可以看出，这是⼀个时间复杂度为多项式的表⽰⽅式。