《算法分析与设计2004春.课件.第10讲》由会员分享，可在线阅读，更多相关《算法分析与设计2004春.课件.第10讲（30页珍藏版）》请在金锄头文库上搜索。
1、1清华大学 宋斌恒1Lecture 10. NP完全性理论清华大学 软件学院宋斌恒清华大学 宋斌恒2内容提要 计算模型与计算复杂度关系 问题分类：【P】与【NP】类 NP难【hard】问题，NP完全集 第一个NPC问题和NPC问题集 如何证明一个问题是NPC问题2清华大学 宋斌恒3涉及到的算法理论基础 原则上是否存在一般数学问题的解题步骤的判 决问题【希尔波特第十问题】 图灵机的停机问题：是否存在一个图灵机，他 可以回答其它图灵机是否停机【既算法是有界 的】 图灵公理：凡是可计算的函数都可以用一台图 灵机来计算 PNPNPC问题定义及其猜想：NPC是一类 不可以在多项式时间内计算的问题。清华大
2、学 宋斌恒4明代数学家程大位著算法统 宗中关于珠算的插图3清华大学 宋斌恒5机械式手动计算机清华大学 宋斌恒6机械计算机 法国数学家、哲学家帕斯卡在1642年发 明了一种机械计算机，并与1649年取得 专利。帕斯卡的计算机采用一种齿轮系 统，其中一小轮转十个数字，下一个小 轮便转动一个数字，通过齿轮系的联 动，可以进行加法和减法的运算. 4清华大学 宋斌恒7图灵 大半个世纪以来，数学家、计算机 科学家提出了各种各样的计算模型 都被证明是同图灵机器等价的。这 一理论已被当成公理，它不仅是计 算机科学的基础，也是数学的基础 之一。为纪念英国数学家Turing (1912-1954) 而设立的图灵奖
3、成为计 算机界的诺贝尔奖. 清华大学 宋斌恒8图灵机模型5清华大学 宋斌恒9图灵机模型 图灵机模型用一个无限长的带子作为无限存储 , 它还有一个读写头 ,这个读写头能在带子上读 , 写和移动 : 开始时 ,带子上只有输入串 ,其它地 方都是空的 .当它需要保存信息时 ,读写头就把 信息写在带子上 .为了读某个输入或写下的信 息 ,带子可能将读写头往回移动到这个信息所 在的地方 .这样读 ,写和移动 ,机器不停的计算 , 直到产生输出为止 .机器实现设置了两种状态 : 接受 或 拒绝清华大学 宋斌恒10图灵机定义 一个图灵机图灵机是一个7元组(Q,q0,q1,q2), 其中Q,都是有穷集合,并且
4、 1)Q 是状态集. 2)是输入字母表,不包括特殊空白符号. 3) 是带字母表,其中: ,是的子 集. 4): QQL,R是转移函数. 5)q0Q是起始状态. 6)q1Q是接受状态. 7)q2Q是拒绝状态,且 q2q16清华大学 宋斌恒11多带图灵机多带图灵机, 和普通图 灵机相似, 只是有多 个带子,每 个带子都 有自己的 读写头,用 于读和写. 如图清华大学 宋斌恒12非确定性的图灵机非确定性的图灵机 非常容易理解,在计算的任何时刻,机器可 以在多种可能性中选择一种继续进行.它 的计算是一课树,不同的分枝对应着机器 不同的可能性.如果某个计算分枝导致接 受状态,则接受该输入.与多带图灵机相
5、同 的是,它的计算能力与普通图灵机也是一 样的.当然他的计算能力就不一样了。7清华大学 宋斌恒13现代计算机模型清华大学 宋斌恒14随机存取机RAM 类似现代计算机，有一个只读输入带、 只写输出带、指令计数器、内存储器、 其零号寄存器用作累加器，内存不能 写，每个内存可以存放任意大的整数。 有12条指令：load、store、add、sub、 mult、div、read、write、jump、jgtz、 jzero、halt。8清华大学 宋斌恒15练习 利用RAM设计一个计算多项式函数求值 的程序：其中多项式为，变 量为x。 考虑问题：程序是什么？输入是什么？ 复杂度是多少？清华大学 宋斌恒1
6、6随机存取存储程序机RASP 除了程序可以存储在存储器中并可以修 改，其它与RAM都一样。9清华大学 宋斌恒17RAM、RASP复杂度耗费标准 均匀耗费：不论计数器内整数多长，其 读写、运算耗费均相等 对数耗费：耗费与其二进制表示的位数 成正比：既与数字大小的对数成正比清华大学 宋斌恒18图灵机模型与RAM模型计算能力 和复杂性关系 定理一、上述计算模型的计算能力等 价：既能够用图灵机计算的问题一定能 够用RAM计算，反之亦然。 定理二、在对数耗费标准下、图灵机与 RAM的计算复杂度可在多项式时间内相 互归约。10清华大学 宋斌恒19问题变换与复杂性归约 利用变换和归约可以把一个问题的复杂 性
7、归结到另一个问题的复杂性 问题A变换到问题B是指： 将问题A的输入变换为问题B的适当输入 求解问题B 把问题B的输出变换为问题A的正确解清华大学 宋斌恒20说明A)(nB： 是指在完成问题 A 到 B的转换过程中的转换过程需要)(nO时间。 通常 n 表示问题 A 的规模， 如果)(n是多项式，则称问题 A 可在多项式时间内变换为问题 B 11清华大学 宋斌恒21变换与归约的关系命题一：若问题 A 的计算时间下界为 T（n） ， 且 A)(nB： 则 T(n)-)(n问题 B 的一个计算时间下界 命题二：若问题 B 的计算时间上界为 T（n） ，且 A)(nB：则 T(n)-)(n问题 A 的
8、一 个计算时间上界 清华大学 宋斌恒22P、NP类定义 PL|L是一个能够在多项式时间内被一 台确定性图灵机所接受的语言 NPL|L是一个能够在多项式时间内被 一台非确定性图灵机所接受的语言 遗留概念说明： 语言 语言与图灵机【算法与图灵机】 为什么选择多项式12清华大学 宋斌恒23A Formal-language framework 形式化语言框架的一些概念简介： Alphabet : is a finite set of symbols A language L over is any set of string made up of symbols from . If = 0,1, t
9、hen L=10,11,101,111,1011, is the language of binary representations of prime numbers, ? is the empty string. ? *=,0,1,00,01,11, is the set of all strings Every language is an element of .清华大学 宋斌恒24Operations on language Union and intersection: same as the set operations Complement of L: Concatenatio
10、n of two language L1and L2: Closure or Kleene Star: L*=U L U L2U L3ULL=*,:221121LxLxxxL=13清华大学 宋斌恒25多项式时间内可求解问题 多项式时间内可求解的问题的特点 多项式时间可求解的问题被认为是易处理 的，有三条理由： 理由1：尽管(n100)算法被认为是不 易处理的，但事实上还没有什么实际问题有 如此之高的多项式算法。 经验证明一但一个问题有多项式解，那 么常常会有更加有效的解决方案。清华大学 宋斌恒26理由2：在某一种计算模型下有多项式算法则 在另一种计算模型下亦有多项式算法。 例如：一个问题在串行
11、随机存取机上有 多项式算法，则在图林机上亦有多项式算 法，在并行机上亦如此。 理由3：多项式算法时间问题集合有非常好的 封闭性质，它在加、乘、复合运算下都是 封闭的 【本课程研究的算法都是多项式的，研究的 问题也是在多项式时间内可解的，对于不 能在多项式时间内求解的问题该如何处 理？】14清华大学 宋斌恒272.抽象问题：（What a problem is)抽象问题Q是集合I和S上的二元关系。其中 I是问题实例集合，S是问题解集合。 例如：最短路径问题：问题实例（G， u、v):一个圆和其上两个顶点；问题解 是（uv)一个从u到v的由边相连的顶点 集。 查找最小值问题：问题实例： a1,an
12、一个数组，问题解:数m。清华大学 宋斌恒28判决问题 Decision问题：如果I0，1或 yes,no，则称问题是判决【决 策】问题，下面我们只关心判决问 题。 优化问题一般都可以转换成判决 问题。15清华大学 宋斌恒293.编码：抽象对象集合S的编码是：抽象对象集合S的编码是： E：S即把S中的对象e转化成一个二进 制（可以是多进制）的串。 如果一个问题的实例是由二进制串集 构成，称其为具体问题。我们称一个算法 在O（T（n)）时间内解决了一个具体问 题，如果此问题i的长度|i|是n，此算法可 在O（T（n)）时间内求解此问题。 一个抽象问题可以编码成具体问题。清华大学 宋斌恒30Prob
13、lem vs. language A decision problem Q can be regarded as a language L: L=x: Q(x)=1 A language accepted by an algorithm A is L=x0,1: A(x)=1 A language decided by an algorithm A if it accepts all string x with A(x)=1 and rejected all string x with A(x)=016清华大学 宋斌恒31Polynomial time We say that a langua
14、ge is accepted in polynomial time by an algorithm A if A accepts every binary string in L in polynomial time We say that a language is decided in polynomial time by an algorithm A if A accepts every binary string in L in polynomial time, and rejects in polynomial time the string not in L清华大学 宋斌恒32De
15、finition of the complexity class P P=L 0,1*: there exists an algorithm A that decides L in polynomial time Theorem 34.2 P=L: L is accepted by a polynomial time algorithm17清华大学 宋斌恒33Polynomial time verifications Verification algorithm A is a two arguments algorithm where one argument is an ordinary input string x and the other is a binary string y called a certificate. A two arguments algorithm A verify an input x if there exists a certificate y such that A(x,y)=1.清华大学 宋斌恒34Language defined by verification L=x in 0,1*: there exists y in 0,1*
