近似算法.ppt

近似算法
黄刘生
2013年9月16日
目录
Part1 NP-完全性理论
Part2 近似算法
3 | Presentation Title | Month 2010
NP-完全性理论
1
计算机科学的局限性
可解性:问题及其可解性可用函数和可计算性来代替
可计算性理论:研究计算的一般性质的数学理论,它通过建立计算的数学模型(例如抽象计算机),精确区分哪些是可计算的,哪些是不可计算的。
可计算函数:能够在抽象计算机上编出程序计算其值的函数。这样就可以讨论哪些函数是可计算的,哪些函数是不可计算的。
Church-Turing论题:若一函数在某个合理的计算模型上可计算,则它在图灵机上也是可计算的。
不可计算性:很多问题和函数是无法用具有有穷描述的过程完成计算
4
停机问题
停机问题:能否写一个程序正确判定输入给它的任何一个程序是否会停机?
设程序halts(P,X)总是正确地判定程序P在其输入X上是否停机:若停机,则返回yes;否则死循环,返回no。设另有一程序:
diagonal(Y){
a: if halts(Y,Y) then
goto a;
else halt;
}
diagonal(diagonal)是否停机? 不可判定
它停机当且仅当halts(diagonal,diagonal)返回否,也就是:
diagonal停机当且仅当它自己不停机,矛盾!
即:halts(P,X)并不存在,停机问题是不可解的!
功能:若halts断定当程序Y用其自身Y作为输入时Y停机,则diagonal(Y)死循环;否则它停机
5
图灵机
依据控制器的状态和读写头所读字符,决定执行以下3个操作之一、之二或全部:
1)改变有限状态控制器中的状态;
2)读写头在相应的方格中写一符号;
3)读写头左、右移一格或不动。
确定型图灵机DTM:若对任一个状态和符号,要执行的动作都是唯一的
非确定型图灵机NTM:若执行的动作是有穷多个可供选择
有单带、多带等变种,计算能力等价
有限状态控制器
输入带
……
无限长
读写头
6
P、NP及NPC类问题
P类问题:一类问题的集合,对 其中的任一问题,都存在一个确定型图灵机M和一个多项式p,对于该问题的任何(编码)长度为n的实例,M都能在p(n)步内,给出对该实例的回答。即:多项式时间内可解的问题
NP类问题:一类问题的集合,对其中的任一问题,都存在一个非确定型图灵机M和一个多项式p,对于该问题的任何(编码)长度为n的实例,M都能在p(n)步内,给出对该实例的回答。
若NTM在每一步都恰有2步可供选择,则回答实例需考察2p(n)种不同的可能性。
存在多项式时间的算法吗?
多项式时间内可验证问题(指验证其解的正确性)
7
P、NP及NPC类问题
多一归约
假设L1和L2是两个判定问题,f将L1的每个实例I变换成L2的实例f(I)。若对L1的每个实例I,I的答案为“是”当且仅当f(I)是L2的答案为“是”的实例,则称f是从L1到L2的多一归约,记作: L1≤mL2(传递关系)
直观意义:将求解L1的问题转换为求解L2的问题,而问题L1不会难于L2
多项式时间多一归约:若f是多项式时间可计算,则上述归约称为多项式时间多一归约,也称多项式时间变换。记作:
8
P、NP及NPC类问题
NPC问题:对于一个(判定性)问题q,若
(1)q∈NP
(2)NP中任一问题均可多项式时间多一归约到q
则称问题q为NP-完全的(plete,NPC)
NP-hard问题:若问题q仅满足条件(2)而不一定满足条件(1),则问题q称为NP-难的(NP-hard,NPH)。显然:NPC⊆NP-hard
NPC和NP-hard关系
NP-hard问题至少跟NPC问题一样难。
NPC问题肯定是NP-hard的,但反之不一定
例:停机问题是NP-hard而非NPC的。
∵该问题不可判定,即无任何算法(无论何复杂度)求解该问题
∴该问题∉NP。但是
可满足问题SAT≤p停机问题
9
P、NP及NPC类问题
NP=?P
∵确定型图灵机是非确定型图灵机的特例,∴P⊆NP
是否有NP⊆P?即是否NP=P?
美国麻省的Clay数学研究所于2000年5月24日在巴黎法兰西学院宣布:对七个“千年数学难题”中的每一个均悬赏100万美元,而问题NP=?P位列其首:


(-,俄罗斯数学家佩雷尔曼在3篇论文预印本中证明了几何化猜想,2006被授予菲尔兹奖)

-米尔斯存在性和质量缺口
-斯托克斯方程的存在性与光滑性
-戴尔猜想
1