2024年-NP完全问题证明幻灯片_第1页
2024年-NP完全问题证明幻灯片_第2页
2024年-NP完全问题证明幻灯片_第3页
2024年-NP完全问题证明幻灯片_第4页
2024年-NP完全问题证明幻灯片_第5页
已阅读5页,还剩30页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

几个NP完全问题12什么是NP完全问题NP完全问题,是世界七大数学难题之一。NP的英文全称是Non-deterministicPolynomial的问题,即多项式复杂程度的非确定性问题。简单的写法是NP=P?,问题就在这个问号上,到底是NP等于P,还是NP不等于P22024/5/5七大数学难题这七个“千年大奖问题”是:NP完全问题、霍奇猜想、庞加莱猜想、黎曼假设、杨-米尔斯理论、纳卫尔-斯托可方程、BSD猜想千年大奖问题美国麻州的克雷(Clay)数学研究所于2000年5月24日在巴黎法兰西学院宣布了一件被媒体炒得火热的大事:对七个“千年数学难题”的每一个悬赏一百万美元。其中有一个已被解决(庞加莱猜想),还剩六个.(庞加莱猜想,已由俄罗斯数学家格里戈里·佩雷尔曼破解。我国中山大学朱熹平教授和旅美数学家、清华大学兼职教授曹怀东做了证明的封顶工作。)32024/5/5什么是NP完全问题NP完全问题排在百万美元大奖的首位,足见他的显赫地位和无穷魅力。在一个周六的晚上,你参加了一个盛大的晚会。由于感到局促不安,你想知道这一大厅中是否有你已经认识的人。你的主人向你提议说,你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟,你就能向那里扫视,并且发现你的主人是正确的。然而,如果没有这样的暗示,你就必须环顾整个大厅,一个个地审视每一个人,看是否有你认识的人。生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是,如果某人告诉你,数13,717,421可以写成两个较小的数的乘积,你可能不知道是否应该相信他,但是如果他告诉你它可以因式分解为3607乘上3803,那么你就可以用一个袖珍计算器容易验证这是对的。人们发现,所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案,都可以在多项式时间内计算,人们于是就猜想,是否这类问题,存在一个确定性算法,可以在多项式时间内,直接算出或是搜寻出正确的答案呢?这就是著名的NP=P?的猜想。不管我们编写程序是否灵巧,判定一个答案是可以很快利用内部知识来验证,还是没有这样的提示而需要花费大量时间来求解,被看作逻辑和计算机科学中最突出的问题之一(斯蒂文·考克于1971年陈述)42024/5/58.5 一些典型的NP完全问题5部分NP完全问题树2024/5/58.5.1合取范式的可满足性问题

(CNF-SAT)6要证明CNF-SAT∈NPC,只要证明在Cook定理中定义的布尔表达式A,…,G或者已是合取范式,或者有的虽然不是合取范式,但可以用布尔代数中的变换方法将它们化成合取范式,而且合取范式的长度与原表达式的长度只差一个常数因子。

问题描述:给定一个合取范式α,判定它是否可满足。如果一个布尔表达式是一些因子和之积,则称之为合取范式,简称CNF(ConjunctiveNormalForm)。这里的因子是变量或。例如:就是一个合取范式,而就不是合取范式。2024/5/58.5.23元合取范式的可满足性问题

(3-SAT)7证明思路:

3-SAT∈NP是显而易见的。为了证明3-SAT∈NPC,只要证明CNF-SAT∝p3-SAT,即合取范式的可满足性问题可在多项式时间内变换为3-SAT。

问题描述:给定一个3元合取范式α,判定它是否可满足。

2024/5/5对于一个合取范式,若每个子句有且仅有3个变元时,它的可满足性问题便称为3SAT问题。定理

3SAT问题属于NPC。下证82024/5/58.5.3团问题CLIQUE

9证明思路:

已经知道CLIQUE∈NP。通过3-SAT∝pCLIQUE来证明CLIQUE是NP难的,从而证明团问题是NP完全的。

问题描述:给定一个无向图G=(V,E)和一个正整数k,判定图G是否包含一个k团,即是否存在,V’

V,|V’|=k,且对任意u,w∈V’有(u,w)∈E。2024/5/58.5.4顶点覆盖问题

(VERTEX-COVER)

10证明思路:

首先,VERTEX-COVER∈NP。因为对于给定的图G和正整数k以及一个“证书”V’,验证|V’|=k,然后对每条边(u,v)∈E,检查是否有u∈V’或v∈V’,显然可在多项式时间内完成。其次,通过CLIQUE∝pVERTEX-COVER来证明顶点覆盖问题是NP难的。

问题描述:给定一个无向图G=(V,E)和一个正整数k,判定是否存在V’

V,|V’|=k,使得对于任意(u,v)∈E有u∈V’或v∈V’。如果存在这样的V’,就称V’为图G的一个大小为k顶点覆盖。2024/5/5

证将3SAT变换到VC.设U={u1,u2,...,un},C={c1,c2,...,cm}是3SAT的实例.如下构造图G,分量设计法.

真值安排分量:Ti=(Vi,Ei),1in,其中Vi={ui,ūi},Ei={{ui,ūi}}任意覆盖必至少包含ui或ūi中的一个,否则不能覆盖边{ui或ūi}.

满足性检验分量:Sj=(Vj’,Ej’),1

j

m,其中

Vj’={a1[j],a2[j],a3[j]}Ej’={{a1[j],a2[j]},{a1[j],a3[j]},{a2[j],a3[j]}}覆盖至少包含Vj’中的两个顶点,否则不能覆盖Ej’中的三角形8.5.4顶点覆盖问题

(VERTEX-COVER)

112024/5/5联络边:

沟通分量之间的关系对于每个子句cj,设cj={xj,yj,zj},则

Ej’’={{a1[j],xj},{a2[j],yj},{a3[j],zj}}G=(V,E)V=(V1

V2

...

Vn)(V1’

V2’

...

Vm’)E=E1

E2

...

En)(E1’

E2’

...

Em’)

(E1’’

E2’’

...

Em’’)K=n+2m显然构造可在多项式时间完成8.5.4顶点覆盖问题

(VERTEX-COVER)

122024/5/5重庆调查公司重庆私人侦探奀莒哔132例如U={u1,u2,u3,u4},C={{u1,ū3,ū4},{ū1,u2,ū4}},则G如下,K=4+2×2=88.5.4顶点覆盖问题

(VERTEX-COVER)

142024/5/5

设V’是V中不超过K的顶点覆盖,则V’中必包含Ti中的一个顶点和每个Ej’中的两个顶点,至少要n+2m个顶点.而K=n+2m,故V’中一定只包含每个Ti中的一个顶点和每个Ej’中的两个顶点.

如下得到赋值

uiV’

t(ui)=T

ūiV’

t(ui)=FEj’’中的三条边有两条被Vj’V’中的顶点覆盖,第三条必被V’

Vi中的顶点覆盖.这表示在Vi中的这个顶点对应的文字取真.所以子句cj被满足.从而C被满足.

设t:U{T,F}是满足C的一组赋值.若t(ui)=T,则在Ti中取顶点ui,否则取ūi.因为t满足子句cj,在Ej’’中的三条联络边中至少有一条被覆盖,那么取Ej’’中的另两条边的端点作为V’中的端点即可.

8.5.4顶点覆盖问题

(VERTEX-COVER)

152024/5/5实例:有穷集A,

a

A,s(a)

Z+.问:是否存在A’

A,使得证:显然均分是NP类问题。下面将3DM变换到均分问题设W,X,Y,M

WX

Y是3DM的实例,其中|W|=|X|=|Y|=q,

W={w1,w2,…,wq}X={x1,x2,…,xq}Y={y1,y2,…,yq}M={m1,m2,…,mk}8.5.5.均分

NPC162024/5/5w1w2…wqx1x2…xqy1y2…yqB的段数与s(ai)一样,每段的最右位为1,其它为0构造A,|A|=k+2对应于每个mi=(wf(i),xg(i),yh(i))有ai.s(ai)为二进制数,分成3q段,每段有p=

log(k+1)

位,共计3pq位,每段对应一个WX

Y中的元素.Wf(i),xg(i),yh(i)

所代表的段的最右位为1,其它为0.注:plog(k+1),2pk+1,k2p

1,

当k个1相加时不会产生段之间的进位令8.5.5.均分

NPC172024/5/5例如:W={w1,w2},X={x1,x2},Y={y1,y2},M={(w1,x2,y2),(w1,x2,y1),(w2,x1,y1)}p=log(3+1)=2元素a1,a2,a3分别对应

(w1,x2,y2),(w1,x2,y1),(w2,x1,y1)s(a1)=010000010001=210+24+20

s(a2)=010000010100=210+24+22s(a3)=000101000100=28+26+22

B=0101010101018.5.5.均分

NPC182024/5/5子集A’={ai:1

i

k}满足

当且仅当M’={mi:ai

A’}是M的匹配A的最后两个元素b1,b2

8.5.5.均分

NPC192024/5/5假设A’

A使得A’和A-A’的元素大小之和相等,即由于b1,b2不在同一子集,8.5.5.均分

NPC202024/5/5反之,若子集M’构成M的匹配,则

A’={b1}

{ai:mi

M’}满足因此A’-{b1}的元素对应的三元组构成M的匹配考虑包含b1的子集A’,必有8.5.5.均分

NPC212024/5/5限制法

三元集合的恰当覆盖(X3C)

最小覆盖问题集中集子图同构问题有界度的生成树

0-1背包Knapsack

多处理机调度8.5.6、NP完全性的证明方法222024/5/5

局部替换法

3SAT

两点间的Hamilton通路问题区间排序分量设计法最小拖延排序8.5.6、NP完全性的证明方法232024/5/5限制法:通过对问题的实例加以限制得到一个已知

NP完全问题的实例.例1三元集合的恰当覆盖(X3C)

实例:有穷集S,|S|=3q,S的三元子集的集合C

问:是否有C’

C,使得S的每个元素恰好出现在C’的一个成员中.

证明:限制

S=WX

Y|W|=|X|=|Y|=qC={{w,x,y}|(w,x,y)W

X

Y}则|C’|=q,且C’中任两个元素都不交,成为3DM问题8.5.6、NP完全性的证明方法242024/5/5例2最小覆盖问题实例:集合S的子集的集合C,正整数K.

问:C是否有S的大小不超过K的覆盖,即是否包含子集C’

C使得|C’|=K且C’=S?证明:限制c

C,|c|=3,|S|=3K,则为X3C问题.例3集中集实例:集合S的子集的集合C,正整数K

问:S是否包含C的大小不超过K的集中集(hittingset),即是否有子集S’

S,使得|S’|K,且S’至少包含C的每个子集的一个元素?证明:限制c

C,|c|=2,令V=S,E=C,则构成图G=(V,E)的顶点覆盖问题.8.5.6、NP完全性的证明方法252024/5/5例4子图同构问题实例:图G=(V1,E1),H=(V2,E2)

问:G中是否有同构于H的子图,即是否有子集V

V1,EE1,使得|V|=|V2|,|E|=|E2|,且存在双射函数f:V2

V,使得

{u,v}

E2

{f(u),f(v)}

E?

证明:限制H为完全图,且|V2|=J,则该问题是团的问题.例5有界度的生成树实例:图G=(V,E),正整数K=|V|1

问:G是否包含一棵顶点度数不超过K的生成树,即是否有子集E’

E,|E’|=|V|

1,图G’=(V,E’)是连通的,且V中每个顶点至多包含在E’的K条边中?证明:限制K=2,则为Hamilton通路问题8.5.6、NP完全性的证明方法262024/5/5例60-1背包Knapsack

实例:有穷集U,

u

U,大小s(u)Z+,价值

v(u)Z+,大小的约束BZ+,价值目标KZ+.

问:是否有子集U’

U,使得证明:限制

u

U,则成为均分问题8.5.6、NP完全性的证明方法272024/5/5例7多处理机调度实例:有穷任务集A,

a

A,长度l(a)Z+,处理机台数

mZ+,截止时间DZ+.

问:是否存在不交的集合A1,A2,…,Am,使得证明:限制则成为均分问题.8.5.6、NP完全性的证明方法282024/5/5局部替换法:选择已知NP完全问题的实例中的某些元素作为基本单元,然后把每个基本单元替换成指定结构,从而得到目标问题的对应实例.

例83SAT

已知问题:SAT

目标问题:3SAT

基本单元:子句

子句集例9两点间的Hamilton通路实例:G=(V,E),u,v

V.

问:G中是否存在一条从u到v的Hamilton通路?已知问题:HC

目标问题:两点间Hamilton通路基本单元:顶点a

u,v

证:对于HC的任一实例,任选顶点a,用u,v代替a,即

G’=(V’,E’),V’=(V{a})

{u,v}E’=(E{{a,v’}|{a,v’}

E})

{{v,v’},{u,v’}|{a,v’}

E}8.5.6、NP完全性的证明方法292024/5/5

GG’G有一条Hamilton回路当且仅当G’有一条从u到v的Hamilton通路替换实例8.5.6、NP完全性的证明方法302024/5/5例10区间排序实例:有穷任务集T,

t

T,开放时间r(t),截止时间d(t),需要时间l(t),其中r(t)N,d(t),l(t)Z+.

问:是否存在关于T的可行调度,即是否存在函数:T

N使得t

T满足:

(t)

r(t)

(t)+l(t)d(t)

t’

T

{t},

(t’)+l(t’)(t)或(t)+l(t)(t’)?

已知问题:均分

目标问题:区间排序基本单元:A中元素

T中的任务312024/5/5实施者,若B为偶数,则存在均分证设A和s(a)

Z+(a

A)为均分的实例.

a

A将a替换成taT,d(ta)=B+1,l(ta)=s(a),其中B为奇数,则不能调度8.5.6、NP完全性的证明方法322024/5/5分量设计法根据目标问题的实例设计分量(分量的成分与目标问题相关),实现已知NPC问题的实例(分量的功能与已

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论