计算理论第六章计算复杂性3

VIP免费

2025-01-13 2 0 1.13MB 55 页 5.9玖币

侵权投诉

计算理论

第6章计算复杂性

P与NP

nP：多项式时间判定

nNP：多项式时间验证

nP？NP悬⽽未决！

nEXP =⋃𝒌TIME(𝟐𝒏𝒌)

nNP⊆ EXP

P=NP

或

NP完全/NPC

n20世纪70年代由库克、列⽂提出

nNP完全：NP中某些问题的复杂性与整个

NP类复杂性关联。这些问题称为NP完全。

nP?NP P?NPC

NPC

可满⾜性问题SAT

n合取范式可满⾜性问题：

n给定⼀个合取范式(cnf),确定这个公式是否可满⾜

nSAT/cnf-SAT = { <

> |

是可满⾜cnf }

n3cnf可满⾜性问题3SAT

n给定⼀个3cnf, 确定这个公式是否可满⾜

n3SAT = { <

> |

是可满⾜3cnf }

库克定理

n定理: SAT ≤𝒎

𝒑"3SAT

n证明思路: 把cnf转化成3cnf

(1)若cnf中⼦句⽂字数小于3，则复制其中⼀

个⽂字，使得⽂字总数达到3；

(2)若cnf中⼦句⽂字⼤于3，则将⼦句分裂为

⼏个⼦句，增加⼀些变元保持原公式的可

满⾜性。

n定理：3SAT ≤𝒎

𝒑"CLIQUE

n证明思路：构造多项式时间函数f，输⼊3cnf，输

出<G,k>。即构造f使得：

n3cnf对应G；

n3cnf的可满⾜赋值对应完全⼦图k；

n公式变量和⼦句模拟G的结构。

设

有k个⼦句，

= (a1

c1)

(a2

c2)

…

(ak

ck).

nG的构造

n每个⽂字对应G⼀个节点

n每个⼦句对应⼀组三个节点

n连接任意两个节点，其中

n同⼀个⼦句内的⼀组三个节点间不连边

n⽂字和⽂字的否定节点间不连边

可满⾜对应G每组节点任选择⼀个真值⽂字对应

的节点构成的完全⼦图

=(x1

x2)

(

Ú¬

x2)

(

x2)

图G可构造如下：

¬x1

¬x1¬x2¬x2

=(x1

x2)

(

Ú¬

x2)

(

x2)

可满⾜赋值01

¬x1

¬x1¬x2¬x2

n证明：设

有k个⼦句，

= (a1

c1)

(a2

c2)

…

(ak

ck).

归约函数f如下构造：

G=<V,E>,

V={a1,b1,c1,…,ak,bk,ck},

E={ (xi,yj) | (i

(xi

yj), xi,yi

{ai,bi,ci}}

往证(1)

可满⾜当且仅当G有k-完全⼦图

(2) f是多项式时间

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

计算理论第6章计算复杂性P与NPnP：多项式时间判定nNP：多项式时间验证nP？NP悬⽽未决！nEXP=⋃!TIME(""!)nNP⊆EXPPNPP=NP或NP完全/NPCn20世纪70年代由库克、列⽂提出nNP完全：NP中某些问题的复杂性与整个NP类复杂性关联。这些问题称为NP完全。nP?NPP?NPCPNPNPC可满⾜性问题SATn合取范式可满⾜性问题：n给定⼀个合取范式(cnf),确定这个公式是否可满⾜nSAT/cnf-SAT={|f是可满⾜cnf}n3cnf可满⾜性问题3SATn给定⼀个3cnf,确定这个公式是否可满⾜n3SAT={|f是可满⾜3cnf}库克定理n定理:SAT≤!"3S...

展开>> 收起<<

计算理论第六章计算复杂性3.pdf

共55页,预览11页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

计算理论第六章计算复杂性3

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: