npc问题详解与实例大全.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：0.60M 资料格式：pdf 举报版权申诉

2fd90257-2180-4d25-b629-f85a01111047.pdf-第1页.png

第1页 / 共68页

2fd90257-2180-4d25-b629-f85a01111047.pdf-第2页.png

第2页 / 共68页

2fd90257-2180-4d25-b629-f85a01111047.pdf-第3页.png

第3页 / 共68页

2fd90257-2180-4d25-b629-f85a01111047.pdf-第4页.png

第4页 / 共68页

2fd90257-2180-4d25-b629-f85a01111047.pdf-第5页.png

第5页 / 共68页

2fd90257-2180-4d25-b629-f85a01111047.pdf-第6页.png

第6页 / 共68页

2fd90257-2180-4d25-b629-f85a01111047.pdf-第7页.png

第7页 / 共68页

2fd90257-2180-4d25-b629-f85a01111047.pdf-第8页.png

第8页 / 共68页

文本预览

NP完全性证明完全性证明六个基本的NPC问题问题六个基本的三元可满足性问题 (3SAT) 三维匹配问题 (3DM) 顶点覆盖问题（VC）团的问题哈密顿回路 (HC) 均分问题基本NP完全问题的证明基本N 完全问题的证明 NP完全问题的证明方法 1

基本完全问题基本NP完全问题: 3SAT 三元可满足性问题：3SAT 实例: 有穷布尔变量集U 和U上的子句集实元可满足性问题句布 U={u1, u2, …, un} C={c1, c2, ... , c } C {c1, c2, ... , cm} 其中|ci|=3, 1≤ i≤ m 问: 对于U 是否存在满足C中所有子句的真值赋值？问: 对于U 是否存在满足C中所有子句的真值赋值？ 2

基本完全问题基本NP完全问题: 3DM 三维匹配问题 3DM 三维匹配问题：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)} 3

基本完全问题基本NP完全问题: VC 顶点覆盖：VC 顶点覆盖：VC 实例: 图G=(V,E), 正整数 K ≤ |V| 问: G中是否存在大小不超过 K 的顶点覆盖, 即是否存在子集问: 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? 使得且 4

顶点覆盖团与独立集问题关系顶点覆盖、团与独立集问题关系设 G = (V, E)为图，V’⊆V, 是G 的补图，则设是的补图则为图 G V’是 G 的顶点覆盖 ⇔ V−V ’是G 的独立集集 ⇔ V−V ’是的团G G 含有大小不超过 K 的顶点覆盖 ⇔ G 中含有大小不小于|V|−K 的独立集 ⇔ 中含有大小不小于|V|−K 的团 G 5

均分基本NP完全问题: HC,均分基本完全问题 HC HC 实例: 图 G=(V,E), |V|=n. 问: G中是否包含一条哈密顿回路, 即是否有G 的顶点问中是否包含条哈密顿回路即是否有的顶点排列 < v j 1 <≤ ni v {, , v j 1 j n } ∈ E ? ,..., j 2 v , vv , { ij j i 1 + v } nj ∈ > 使得 E 1, 均分实例: 有穷集合 A, ∀a∈A 有 “大小” S(a)∈Z+ 问: 是否存在子集 A’⊆A 使得 aS )( )( ∑ ∑ Aa ' ∈ aS )( )( ∑= ∑ AAa ' −∈ 6

归约次序归约次序 SAT 3SAT 3SAT 3DM VC 均分 HC 团（独立集） 7

证明证明：3SAT∈NPC 思路思路： 3SAT∈NP 将SAT的实例变换成 3SAT 的实例将SAT的实例变换成 3SAT 的实例根据子句中的文字个数 k 分别处理 1个子句转变成多个子句保证每个子句含有3个文字转变前与转变后的真值不变证显然3SAT属于NP 设 U={u1, u2, ... , un}, C={c1, c2, ... , cm}是 SAT的任何实例 n}, 的任何实例 , m}是 { 1, 2, 设 { 1, 对于C中任意子句 2, , cj = { z1, z2, ... , zk } j 构造新增的变量集Uj’和子句集Cj’ k 1 2 8

分享到：

赞收藏

资料库

npc问题详解与实例大全.pdf

相关推荐

课程资源

热门标签

最新资料