算法第9章 NP完全性理论

第9章

NP完全性理论与近似算法1学习要点理解RAM，RASP和图灵机计算模型理解非确定性图灵机的概念理解P类与NP类语言的概念理解NP完全问题的概念理解近似算法的性能比及多项式时间近似格式的概念通过范例学习NP完全问题的近似算法（1）顶点覆盖问题；（2）旅行售货员问题；（3）集合覆盖问题；（4）子集和问题。2在计算机算法理论中，最深刻的问题之一是：从计算的观点来看，要解决的问题的内在复杂性如何，它是“易”计算的还是“难”计算的。若知道了一个问题的计算时间下界，就可以较正确地评价解决该问题的各种算法的效率，进而确定对已有算法还有多少改进的余地。在许多情况下，要确定一个问题的内在复杂性是相当困难的。但问题的计算复杂性可以通过解决该问题所需计算量的多少来度量。3如何区分一个问题是“难”还是“易”？人们通常将在多项式时间内解决的问题看作是“易”解决的问题，而将需要指数时间解决的问题看作是“难”问题。（这里是针对问题的规模而言）对于实际遇到的很多问题，人们至今未确切地了解其内在的计算复杂性。只能用分类的方法,将计算复杂性大致相同的问题,归类研究。4计算模型在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算。建立计算模型的目的,是为了使问题的计算复杂性分析,有一个共同的客观尺度。3个基本计算模型：随机存取机RAM(RandomAccessMachine)；随机存取存储程序机RASP(RandomAccessStoredProgramMachine)图灵机(TuringMachine)。这3个计算模型在计算能力上是等价的，但在计算速度上是不同的。5NP完全问题6新千年的七个数学问题

1900年在巴黎召开的“国际数学家大会”上,Hilbert提出著名的23个数学问题,深刻影响(和推动)了20世纪的数学发展.在新千年来临之际,2000年5月24日，就在希尔伯特提出23个世纪难题之后的整整一百年后,在巴黎又宣布了新的7个数学问题.这次是由“柯莱数学研究所”(/,ClayMath.Inst.,Cambridge,MA,USA,)宣布,为7个问题中的任一个解答设立一百万美元奖金.

7在这7个问题中，排在第一位的是P与NP问题。即P－问题是可被“运行多项式时间的”一个算法解决的问题(多项式时间:运行时间最多是输入量的多项式函数).NP－问题即是有一个“可用多项式时间检验的”解答的问题.P=NP?

8

2．

黎曼假设

(Riemann

Hypothesis):

黎曼Zeta－函数的非平凡零点的实部都是1/2

.

3．庞加莱猜想

(Poincare

Conjecture):

任意闭单连通3-流型同胚于3-球.

4．霍奇猜想

(Hodge

Conjecture):

在非奇异复射影代数簇上,

任一霍奇类是代数闭链类的有理线性组合.

5．BSD猜想

(Birch

and

Swinnerton-Dyer

Conjecture)

6．奈维尔－斯托克斯方程

(Navier-Stokes

Equatoins)

7．杨－米尔斯理论

(Yang-Mills

Theory):

证明诸量子杨－米尔斯场存在而且有一个大缺口.9背景计算机处理能力受限于内存大小与中央处理器速度等，导致算法本身的数据结构对于其执行效率有很大的影响。在分析算法时，主要以时间复杂度与空间复杂度两者为分析依据。随着计算器发展迅速，算法的空间复杂度已经不是那么重要的一件事，目前分析主要是在时间复杂度方面。10P问题：线性时间或者多项式时间内能够解决的问题。如能够在O(n)、O(nlog2n)、O(nk)数量级内解决的问题。它们都是以多项式时间为上界。NP问题：不能在多项式时间内解决的问题。如计算时间数量级为O(n!)、O(2n)。不可解问题：“图灵停机问题”任何计算机耗费任意时间不能解决。逻辑学家阿朗索·丘奇证明了所谓的判定问题也是不可解的：判定一个已知的语句是否表达一个算术的真值，决不可能有一般的过程。换句话说，能够输出所有算术真值的计算机是不存在的

。P与NP问题11图灵、图灵奖及图灵奖获得者简介1912年6月23日，出生于英国伦敦。1931年-1934年，在英国剑桥大学国王学院学习。1932年-1935年，研究量子力学、概率论和逻辑学。1935年，由于独立发现中心极限定理，获Smith奖，年仅23岁被选为剑桥大学国王学院院士。1936年，研究可计算理论，提出“图灵机”的构想。121936年-1938年，主要在美国普林斯顿大学做博士研究，涉及逻辑学、代数和数论等领域。1938年-1939年，返回剑桥从事研究工作，并应邀加入英国政府破译二战德军密码的工作。1940年-1942年，作为主要参与者和贡献者之一，在破译纳粹德国通讯密码的工作上成就杰出，并成功破译了德军U-潜艇密码，为扭转二战盟军的大西洋战场战局立下汗马功劳。131943年-1945年，担任英美密码破译部门的总顾问。1945年,应邀在英国国家物理实验室从事计算机理论研究工作。1946年，图灵在计算机和程序设计原始理论上的构思和成果，已经确定了他的理论开创者的地位。由于图灵的杰出贡献，他被英国皇室授予OBE爵士勋衔。1947年-1948年，主要从事计算机程序理论的研究，并同时在神经网络和人工智能领域做出开创性的理论研究。141948年，应邀加入英国曼彻斯特大学从事研究工作，担任曼彻斯特大学计算实验室副主任。1949年，成为世上第一位把计算机实际用于数学研究的科学家。1950年，发表论文“计算机器与智能”，为后来的人工智能科学提供了开创性的构思。提出著名的“图灵测试”理论。151951年，提出生物增长的非线性理论研究。年仅39岁即被选为英国皇家学会会员。1953年-1954年，继续在生物和物理学等方面的研究。1954年6月7日，42岁，图灵死于家中的床上，床头有一个咬了一半的、在氰化物溶液中浸泡过的苹果，警方调查结论是自杀。一代英灵，就此过早离去，成为人类科学史上的一大遗憾。16TuringAward被公认为是计算机科学界的诺贝尔奖——最高奖项.奖励在计算机科学技术研究中做出了创造性贡献的杰出科学家.1966年开始由ACM(AssociationforComputingMachinery)设立（美国计算机协会，1947年成立，与IEEE(InstituteofElectricalandElectronicsEngineers(IEEE)美国电气和电子工程师协会)ComputerSociety并列为计算机界最著名的两大国际学术组织），用Turing的名字来命名该奖，以纪念这位伟人对于计算机科学技术发展的功绩。17通常每年1名获奖者,偶尔2名(同方向)，02年3名(RSA,Rivest,Shamir,Adelman).虽未明确规定,但授奖较偏重于计算机科学理论和软件技术方面作出贡献的科学家.唯一华人获奖者是姚期智(AndrewYao,美籍,2000年)1972，E.W.Dijkstra（美Burroughs公司）：求最短路径的Dijkstra算法，PV操作，结构化程序设计，“goto有害”等181974，D.E.Knuth（stanford）：算法最早的奠基人之一，现代“算法”与“数据结构”等名词及内涵的提出，KMP算法，多卷算法巨著的作者，LR(k)文法，Tex编辑器等。1976，M.O.Rabin（以色列人）&D.S.Scott（英国人）师兄弟（导师A.Church）：非确定有穷自动机的提出、判定问题等。Rabin：计算复杂性概念的雏形、随机算法的思想奠定、寻找及判定素数算法、单向函数等。Scott:语义学等。1978，R.W.Floyd（Stanford）：Heap-sort算法、求最短路径的Floyd动态规划算法等，编译及优化（优先文法等），程序正确性证明等。191982，S.A.Cook（加Toronto大学）：“NP-完全”概念的提出与理论的奠定，算法复杂性等。1984，N.Wirth（瑞士苏黎世高工）：“程序=算法+数据结构”，结构化程序设计分、创始人，ExtendedBNF等,“Pascal之父”。.1985，R.M.Karp（UC-Berkeley）：计算机系、数学系、工业工程运筹学系“三栖教授”，哈佛文学士、理学硕士、数学博士。分枝限界法的创始人（与Held），Rabin-Karp子串匹配算法，求网络最大流的Edmonds-Karp算法，NP-完全理论（Karp规约等），随机算法，并行算法等。201986，J.E.Hopcroft(Cornell)&R.E.Tarjan（Princeton）：图论算法(e.g.深度优先算法，连通性、平面图判定),数据结构Hopcroft：形式语言与自动机名著作者（与Ullman），算法名著作者（与Aho、Ullman），算法好坏的衡量尺度（渐进时间复杂性），2-3树，机器人等。Tarjan：D.E.Knuth的博士生，集合的Union-find算法，平摊分析，持久性数据结构及各种数据结构（e.g.动态树、”八字型”树，自调整结构）.211993，J.Hartmanis(Cornell)&R.E.Stearns(Albany)：计算复杂性理论的主要奠基人：系统化的理论体系及命名。Hartmanis：Hartmanis矩阵乘法，Hartmanis快速离散傅立叶变换。Stearns：首先提出将上下文无关文法理论应用于编译器设计等。2000，AndrewYao（姚期智，Princeton，现在清华）：计算复杂性，量子计算，密码学（e.g.单向函数）、通信理论等。2002，RonaldL.Rivest,AdiShamir,LeonardM.Adelman：公共密钥算法（RSA算法是当前在互联网传输、银行以及信用卡产业中被广泛使用的安全基本机制）.22图灵机A.Turing在1936年介绍了这样一个通用的计算模型，该模型具有以下两个性质：该模型的每个过程都是有穷可描述的；过程必须是由离散的、可以机械执行的步骤组成。图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力。通过研究TM来研究递归可枚举集和部分递归函数,为算法和可计算性研究提供了形式化描述工具。23FinitecontrolX1BB...X2XnXi带（tape）单元格（cell）带符（tapesymbol）读写头在每一时刻扫描带上的一个单元带有一个最左单元，向右则是无限的。带的每个单元可容纳一个带符号开始时，最左边n个单元装着输入（n>＝0，n为有限数），它是一个字符串，符号都选自“带符号”的一个子集，即所谓的“输入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊的带符号，但不是输入符号。图灵机的基本模型24图灵机的工作机制在一个图灵机的动作中，图灵机根据带头（读写头）所扫描的符号和有限控制器的状态可能作改变状态在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号.将带头向左或者右移一个单元。*图灵机和双向有限自动机的区别：图灵机能改变它带上的符号。25图灵机的形式化描述

有限状态集

有限输入符号集

有限带符号集

转移函数

开始状态

特殊带符:空白符

终态集合q0

Q

T

B

–T

F

Q转移函数:Q

Q

{L,R}形式定义一个图灵机

TM(Turingmachine)是一个七元组

M=(Q,T,

,

,q0,B

,F).

26δ函数示例：

Q×∑→Q×∑×{L,R}δ(q,ai)=(p,B,L)q,p∈Qδ(q,ai)=(p,b,R)ai∈∑b∈∑

格局用w1qw2描述图灵机的瞬间工作状态（瞬像）q为M的当前状态，w1w2∈∑*w1w2是当前时刻从开始端（因为可写）到右边空白符号为止的内容当读写头已达到带的右端，则w1w2为读写头以左的内容。约定：w1qw2表示读写头正扫描w2的最左字符 w2＝

则表示读写头正扫描一个空白字符。图灵机的函数与格局27给定图灵机M=(Q,T,

,

,q0,B

,F)，定义格局之间的推导关系├M

如下：1.设

(q,Xi)

=(p,Y

,L)，则有X1X2…Xi-1qXiXi+1…Xn

├MX1X2…Xi-2pXi-1Y…Xn

，

但有如下两个例外

：（1）i=1时，qX1X2…Xn

├MqYX2…Xn

，和（2）i=n及Y=B时，X1X2…Xn-1qXn

├MX1X2…Xn-2pXn-1B.282.设(q,Xi)

=(p,Y,R)，则有

X1X2…Xi-1qXiXi+1…Xn

├MX1X2…Xi-1YpXi+1…Xn

，但有如下两个例外

：（1）i=n时，X1X2…Xn-1qXn

├MX1X2…Xn-1YpB，和（2）i=1及Y=B时，qX1X2…Xn├MBpX2…Xn-1Xn29图灵机接受的语言L(M)={ω│ω∈T*且q0ω├*α1pα2,p∈F,α1α2∈∑*}图灵机接受的语言是输入字母表中这样一些字符串的集合，初始时，这些字符串放在M的带上，M处于状态q0，且M的带头处在最左单元上，这些字符串将使M进入某个终止状态。假定：当输入被接受时，图灵机将停止，没有下一个动作。30任给图灵机M=(Q,T,

,

,q0,B

,F)，以及输入字符串wT*.试问：对于w，M是否停机？停机是指图灵机不存在下一个移动步（move）.

结论:图灵机的停机问题是不可解的（即不可判定的）.

结论:任给图灵机M

，很容易构造一个图灵机M

，使得L(M)=L(M

)，并满足：如果w

L(M)

，则对于w，M

接受w并一定停机.如果没有特别指出，总是假定图灵机到达终态（接受态）后一定停机.但是，对不能接受的字符串，图灵机可能永不停止.（只要M还在某个输入上运行，无法知道是因为运行的时间不够长而没有被接受，还是根本就不会停机）

图灵机的停机问题

31图灵机举例例1：设语言L={anbn│n>=1}，设计图灵机接受L。思路：最初带上为aa…abb…bBBB…… n个an个b首先用x替换M最左边的a，再右移至最左边的b用y替换之，左移寻找