null§5.6 基本NP完全问题的
证明
住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问
§5.6 基本NP完全问题的证明null定理1 三可满足问题(3SAT)是NP完全问题。
(证) 整个证明过程分成两步，
先证 3SAT∈NP，
再证明SAT ∝ 3SAT．
3SAT ∈ NP是显然的，因为很容易构造一不确定算法，
该算法第一阶段猜一个函数
f： U→{真, 假}。null然后，第二阶段检测公式F的值，
这只需将公式F中的所有因子u及⌉u分别用f(u)和f(u)的补替代，
即用“真”或“假”替代，
再对逻辑式求值。
容易看出，第二阶段所需时间是m和n的多项式
其中m是集合U的逻辑变量的个数，
n是公式F的项的个数。nullSAT ∝ 3SAT就不那末明显了。
先构造映射
g：SAT → 3SAT
其中SAT
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示可满足性问题的实例之集合
3SAT表示三可满足性问题的实例的集合。
然后再证明g是多项式转换。
SAT的实例为
①集合U＝{u1,u2,…,um}
②公式F＝{c1,c2,…,cn}，
其中ci (i＝1，2，…，n)是项。
以U及F为输入，g为3SAT构造实例U′及F′如下所述:nullU′ = U ∪ U′1 ∪ U′2 ∪ … ∪ U′n
F′ = C′1 ∪ C′2 ∪ … ∪ C′n
其中C′j 是项的集合，且每一项含三个因子
因此F′也是项的集合，所以F′是公式。
由上两式可见:
逻辑变量集合U增加一些变量，
再改写公式F的每一项为项集合，
就得到三可满足问题的实例。
还需证明F′是可满足的充分必要条件为
F是可满足的。null为定义映射g，只须说明如何构造C′j 及U′j .
公式F的项Cj是因子的集合
Cj ＝{Z1，Z2，…，ZK }
即| Cj |＝K， Cj由K个因子组成。
C′j 及U′j的构成按K的值
分四种情况讨论。nullK＝l， Cj ＝ {z1}，则U′j及C′j构造为
U′j ＝ {yj1, yj2 }
增加两个逻辑变量而已
C′j＝{{z1,yj1, ⌉yj2},{z1, ⌉yj1,yj2 },{z1, yj1,yj2 },
{z1, ⌉yj1, ⌉yj2 }}
即C′j含四个项。
将Cj一个项替换为四个项.
注意: 这四个项穷尽两个逻辑变量yj1, yj2
的四种情况nullK＝2， Cj ＝{z1 ，z2}，则
U′j ＝ {yj}
仅仅增加一个逻辑变量
C′j ＝ { {z1，z2，yj}，{z1，z2，⌉yj}}
即C′j含两项。
将Cj一个项替换为两个项.
注意: 这两个项穷尽一个逻辑变量yj
的两种情况nullK＝3， Cj ＝{z1 ，z2 ，z3}，则
U′j ＝ Φ
不增加逻辑变量
C′j ＝ { {z1 ，z2 ， z3}}
即C′j含一项。nullK>3， Cj ＝{z1,z2 ,…,zk }，则
U′j ＝ {yj1,yj2 ,…,yjk-3 }, 增加K - 3个逻辑变量
C′j ＝{ {z1,z2 ,yj1} ,
{z3, ⌉yj1,yj2},
{z4, ⌉yj2,yj3}, …,
{z i-1, ⌉yji-3,yji-2},
{z i , ⌉yji-2,yji-1},
{zi+1, ⌉yji-1,yji},…,
{zk-2, ⌉yjk-4,yjk-3},
{zk-1,zk ,⌉yjk-3}}
即C′j含(K一2)项, 比| U′j |大1。
若K=4, 则含两项.若K=4, 则增一个变量
第一项和最后一项各含两个z(原变量)和一个y(新增变量).
其余各项含一个z和两个y(其中一个是因子的非)null显然，映射g为3SAT问题计算一个实例所需时间为m和n的多项式。
要增加n个变量集合, 对应F中的n个项.
每个集合至多含m-3个变量, m为U中因子的个数
要把n个项改写为n个 项集合
每个集合至多含m-2个项, 每项有三个因子.
null现在证明如F可满足, 则F′也可满足. 设
f： U→{真, 假}
能使F值为真。
因U是U′的子集, 只须证明f可以扩展为
f′： U′→{真, 假}
并使公式F′为真；
从而只要给诸U′j的各逻辑变量赋值
保持U的逻辑变量的赋值不变,
并使F′为真即可null因集合
(U′－U)
中的逻辑变量被划分为集合U′j ，
U′j中的逻辑变量仅出现在相应的C′j中,
因此只须证明，
映射f′可以逐次扩展到各集合U′j，
每次扩展使C′j中的项的值都为真．null同样分四种情况，
①K＝1，
用数理逻辑的方法很容易证明C′j和Cj恒等，(P7)
即C′j的值只与z1有关，
因f已经满足Cj ，
则f′不论给yj1, yj2赋什么值都能使C′j满足。null②K=2，同样可用数理逻辑
证明C′j和Cj恒等，
即C′j的值只与z1 ，z2有关，
因f已经满足Cj，
则不论f给yj赋什么值, 都可使C′j满足null③K=3，(P9)
U′j为空，
且C′j只含一个项, 就是Cj, 已被f满足。
Cj已经含三个因子, 被f赋值，
因此f, 不用给任何新逻辑变量赋值。
null④K>3，
Cj= {z1,z2 ,…,zk }，因f已满足Cj，
此即Cj的K个因子中至少一个为真，
设zi为真，
按i的值分三种情况,
讨论如何扩展映射fnull(ⅰ) i为1或2，则令
yj1=yj2 =…= yjK-3=假
这使C′j的每一项都为真。
(ⅱ)如i为K－4或K －3，则令
yj1=yj2 =…= yjK-3= 真
这也使C′j的每一项都为真。
(ⅲ)如2
3，
f′满足C′j，则只须证明f′使
z1，z2，···，zk
中至少有一个的值为真。用反证法.
令
z1,z2 ,…,zk
皆假, 用“假”替代C′j中的诸z，再简化C′j
则C′j等价为
nullC′j ＝{ {yj1} ,
{⌉yj1,yj2},
{⌉yj2,yj3}, …,
{⌉yji-3,yji-2},
{⌉yji-2,yji-1},
{⌉yji-1,yji},…,
{⌉yjk-4,yjk-3},
{⌉yjk-3}}
因C′j被满足，则其各项之值皆“真”。
第一项之值为真，则必有
f′(yj1)＝真
null第二项{⌉yj1,yj2}等价于{yj2}，其值为真，则必有
f′(yj2)＝真
以此类推，由Cj的倒数第二项为“真”知，必有
f′(yjK-3) ＝真
但是由此确定的映射没能满足C′j
因为C′j的最后一项
{⌉yjk-3}
必定为假，从而使C′j值为假，即公式F′值为假，这与f′满足F′的假设矛盾。null这反证了Cj中诸因子
z1,z2 ,…,zk
至少有一个为真，这使Cj值为真. 因此映射f使公式F满足。证毕。null定理2 顶点覆盖问题(VC)是NP完全问题。
证明过程梗概
先定义3SAT ∝ VC的多项式转换f.
3SAT问题的实例为两个集合
U＝ {u1,u2,…,un}
F＝ {C1,C2,…,Cm}
其中Ci(i=1，2，…，m)为含三个因子的项
null由3SAT的实例, 映射g构造VC问题的实例有以下四步骤。
①对每一个逻辑变量ui∈ U，构造子图
该子图由两个节点ui ，⌉ui 及一条边组成。
ui⌉uinull②对每一项Ci∈ F构造子图
vi2
vi1 vi3
以Ci的三个因子为顶点,
建造一个三角形(有三条边)
null③对项Ci＝{vi1,vi2 ,vi3}中每个因子
vij(j＝1, 2, 3),
如vij＝u (u ∈ U)，
则连接节点u(由①构造)和节点vij(由②构造)
如vij＝ ⌉u，
则连接节点⌉u和节点vij
由以上三步得到VC实例的图。
④令K=n+2m, n=|U| m=|F|null证明之前, 给一个例子.null设3SAT问题有如下实例
U = {u1，u2，u3，u4}
F＝ {{ul，⌉u3， ⌉u4}，{⌉ul，u2， ⌉u4}，
{u2，u3，u4}}
ul ⌉ul u2 ⌉u2 u3 ⌉u3 u4 ⌉u4
K=10
显然实例是可满足的，f如上所示。真 真 假 假null 为证明本定理,须证明两件事.
⒈ VC ∈ NP
设VC问题的实例G = (V, E)
构造一不确定算法，该算法第一阶段猜一个V′⊂V(V′是V的子集,且|V′|=K)
第二阶段检测V′是否为G的K覆盖.
这阶段的时间复杂度是多项式的.
所以VC问题可由多项式时间不确定算法解决
因此,VC ∈ NPnull⒉ 前面定义的映射g是从3SAT到VC的多项式转换。
g的四步骤的时间复杂度都是多项式的
所以g的复杂度也是多项式的
下面证明3SAT的实例可满足的充分必要条件是:
它在VC的像实例有K覆盖.null先设3SAT问题的实例可满足,欲证明其在VC的像实例有K覆盖
存在映射f, 给逻辑变量集合U的各个u赋值, 使得F的所有项
C1,C2,…,Cm
的值均为真.
构造VC的像实例的K覆盖如下.null考虑每一个逻辑变量u,
若映射f给u的赋值为真, 则将①构造的线段的左侧端点选入覆盖
否则, 把右侧端点选入覆盖
入选的有n个结点
它们覆盖了①构造的n条线段null又因为②的构造方法, 每个项
Ci＝{vi1,vi2 ,vi3}
的三个因子至少一个(记作v)的值为真.
v对应着②构造的子图中的一个结点,
除去它,将另两个结点选入覆盖,
它们覆盖了三角形的三条边
共选入了2m个结点
(该项对应着②构造的子图——三角形)
null
v是三角形中的一个结点,
它和①的线段的一端相连接.
总共选入了n+2m个结点.
将证明这构成了VC实例的K覆盖.
null由①构造的n条线段和②构造的三角形的3m条边已经被它们覆盖
下面证明③连接的3m条边也被覆盖
每个三角形有两个结点被选入, 相应的两条边被覆盖
第三个结点(v)没有被选入,但是与之相连的、在①的线段里的端点被选入.
所以, 第三条边也被覆盖了.
null充分性得证, 下面证明必要性
先设其在VC的像实例有K覆盖,
欲证明3SAT问题的实例可满足null注意到K=n+2m
考虑由①建造的线段,
每条线段的两端点必有一端在K覆盖,否则该线段无法覆盖
共n个结点
由此定义映射f(u)如下:
若与u对应的线段的左侧结点在覆盖则
f(u)=真
否则f(u)=假null考虑由②建造的三角形,
为覆盖这三边, 必有两个顶点在K覆盖, 共2m个结点.
注意: 已经有了n+2m=K个结点.
考虑由③添加的三条线段,
三角形有两个顶点在K覆盖, 与之相连的两线段则被覆盖,
第三个顶点v没有入选K覆盖,
null所以由③添加的第三条线段的覆盖责任,必定由不在三角形的端点u承担
这个端点u必定就是前一页的入选端点,
若这个端点是线段的左侧结点则
该结点对应的逻辑变量赋值为真
第三顶点v的赋值为真;
若这个端点是线段的右侧结点则
该结点对应的逻辑变量赋值为假
第三顶点v的赋值也为真null所以, 三角形对应的项的逻辑值因而为真
所以公式F的值也就是真
所以3SAT的实例可满足.
证毕null定义 图G＝(V, E)的独立集合V′是V的子集
且如u、v ∈ V′，则(u，v) ∉ E，
即V′中的任两个节点之间不存在边。
如|V′|＝K，则V，称为G的K独立集合。
独立集合问题(简称IS)
实例：图G＝(V，E)及正整数J≤|V|
问：G是否有独立集合V′且|V′| ≥ Jnull引理 图G＝(V，E)， V′是V的子集V′ ⊂V.
下述三命题是等价的：
1. V′是G的覆盖
2. (V—V′ )是G的独立集合
3. (V—V′ )是G的补图G′ ＝(V，E′)的集团, 其中
E′＝ {(u, v) | u、v∈ V，(u，v) ∉ E}
引理通过独立集合将覆盖与集团联系起来null证 引理可以分三步来证明
① ② ③
l ⇒ 2 ⇒ 3 ⇒ 1
①l ⇒ 2, 使用反证法
设(V—V′ )不是G的独立集合
则存在两点u、v ∈ (V—V′ ), 但是
(u, v ) ∈ E
因为u、v ∈ (V—V′ ),所以
u、v ∉ V′
这与“V′是G的覆盖”矛盾(V′没有覆盖边(u, v ))
null②2 ⇒ 3
(V—V′ )是G的独立集合
任意两点u、v ∈ (V—V′ ),
则(u, v ) ∉ E
根据补图的定义, 有(u, v ) ∈ E′,
所以, (V—V′ )是G的补图G′ ＝(V，E′)的集团null③ 3 ⇒ 1
(V—V′ )是G的补图G′ ＝(V，E′)的集团,
用反证法证明V′是G的覆盖。
设V′不是G的覆盖，则
G中存在边(u，v) ∈ E，但是
u ∉ V′，v ∉ V′，
则必有
u ∈ V—V′, v ∈ V—V′，
因(V—V′)是G′的集团，则
(u，v) ∈ E′
由补图定义知
(u，v) ∉ E
这与前面假设矛盾。定理证毕.null引理告诉我们, 覆盖、独立集合、集团三者只是同一个问题的不同叙述。
上述引理提供了极为简单的方法，
可将一个问题转换为其它两个问题。譬如，
欲将顶点覆盖问题转换为集团问题，只需映射
f：VC → CL
由VC的实例：G＝(V, E)及正整数K，映射f构造CL的实例：图G′(G的补图)和
正整数J＝|V|—K．null因此只要证这三个问题中一个是NP完全问题
就证明了三个问题都是NP完全问题.
由定理2可证得定理3。
定理3 集团问题(CL)和独立集合问题(IS)是NP完全问题null定理4 哈密尔顿回路问题(HC)是NP完全问题
下一节§5-8给出定理的完整证明
先用定理4的结论证明巡回售货员问题(TS)
是NP完全问题。null定理5 巡回售货员问题(TS)是NP完全问题
定理5的证明很简单，本章第四节的例子已经证明
HC ∝ TS
又TS ∈ NP是明显的，
定理4结论为
哈密尔顿问题(HC)是NP完全问题，
所以TS问题是NP完全问题
浙公网安备 33021202002483