中科大算法第二章近似算法--黄刘生(调整后适合打印版).ppt

近似算法黄刘生2013年9月16日目录Part1NP-完全性理论Part2近似算法*|PresentationTitle|Month2010NP-完全性理论1*计算机科学的局限性可解性:问题及其可解性可用函数和可计算性来代替可计算性理论:研究计算的一般性质的数学理论,它通过建立计算的数学模型(例如抽象计算机),精确区分哪些是可计算的,哪些是不可计算的。可计算函数:能够在抽象计算机上编出程序计算其值的函数。这样就可以讨论哪些函数是可计算的,哪些函数是不可计算的。Church-Turing论题:若一函数在某个合理的计算模型上可计算,则它在图灵机上也是可计算的。不可计算性:很多问题和函数是无法用具有有穷描述的过程完成计算*停机问题停机问题:能否写一个程序正确判定输入给它的任何一个程序是否会停机?设程序halts(P,X)总是正确地判定程序P在其输入X上是否停机:若停机,则返回yes;否则死循环,返回no。设另有一程序:diagonal(Y){a:ifhalts(Y,Y)thengotoa;elsehalt;}diagonal(diagonal)是否停机?不可判定它停机当且仅当halts(diagonal,diagonal)返回否,也就是:diagonal停机当且仅当它自己不停机,矛盾!即:halts(P,X)并不存在,停机问题是不可解的!功能:若halts断定当程序Y用其自身Y作为输入时Y停机,则diagonal(Y)死循环;否则它停机*图灵机依据控制器的状态和读写头所读字符,决定执行以下3个操作之一、之二或全部:1)改变有限状态控制器中的状态;2)读写头在相应的方格中写一符号;3)读写头左、右移一格或不动。确定型图灵机DTM:若对任一个状态和符号,要执行的动作都是唯一的非确定型图灵机NTM:若执行的动作是有穷多个可供选择有单带、多带等变种,计算能力等价有限状态控制器输入带……无限长读写头*P、NP及NPC类问题P类问题:一类问题的集合,对 其中的任一问题,都存在一个确定型图灵机M和一个多项式p,对于该问题的任何(编码)长度为n的实例,M都能在p(n)步内,给出对该实例的回答。即:多项式时间内可解的问题NP类问题:一类问题的集合,对其中的任一问题,都存在一个非确定型图灵机M和一个多项式p,对于该问题的任何(编码)长度为n的实例,M都能在p(n)步内,给出对该实例的回答。若NTM在每一步都恰有2步可供选择,则回答实例需考察2p(n)种不同的可能性。存在多项式时间的算法吗?多项式时间内可验证问题(指验证其解的正确性)*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是多项式时间可计算,则上述归约称为多项式时间多一归约,也称多项式时间变换。记作:*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-hardNPC和NP-hard关系NP-hard问题至少跟NPC问题一样难。NPC问题肯定是NP-hard的,但反之不一定例:停机问题是NP-hard而非NPC的。∵该问题不可判定,即无任何算法(无论何复杂度)求解该问题∴该问题∉NP。但是可满足问题SAT≤p停机问题*P、NP及NPC类问题NP=?P∵确定型图灵机是非确定型图灵机的特例,∴P⊆NP是否有NP⊆P?即是否NP=P?美国麻省的Clay数学研究所于2000年5月24日在巴黎法兰西学院宣布:对七个“千年数学难题”中的每一个均悬赏100万美元,而问题NP=?P位列其首:(-,俄罗斯数学家佩雷尔曼在3篇论文预印本中证明了几何化猜想,2006被授予菲尔兹奖)---戴尔猜想