内容提要 ·计算模型与计算复杂度关系 NP完全性理论介绍 ·问题分类:【P】与【NP】类 NP一难【hard】问题,NP完全集 清华大学 ·第一个NPC问题和NPC问题集 宋斌恒 ·如何证明一个问题是NPC问题 清华大学宋域恒 请华大学宋恒 引言 NPC问题 ·脑力劳动机械化【吴文俊先生】 ·P一NP一NPC问题定义及其猜想:NPC是 图灵机的停机问题:是否存在一个图灵机,他 类不可以在多项式时间内计算的问 可以回答其它图灵机是否停机【既算法是有界 题 的】 原则上是否存在一般数学问题的解题步骤的判 ·如果在量子计算模型中上述问题又如 决问题【希尔波特第十问题变种】 图灵公理:凡是可计算的函数都可以用一台图 灵机来计算 清华大学末斌恒 请华大学宋恒 下面介绍计算机械化的进程 明代数学家程大位著《算法统 宗》中关于珠算的插图 :a(m/ 清华大学末破恒 请华大学宋
1 清华大学 宋斌恒 1 NP完全性理论介绍 清华大学 宋斌恒 清华大学 宋斌恒 2 内容提要 • 计算模型与计算复杂度关系 • 问题分类：【P】与【NP】类 • NP－难【hard】问题，NP完全集 • 第一个NPC问题和NPC问题集 • 如何证明一个问题是NPC问题 清华大学 宋斌恒 3 引言 • 脑力劳动机械化【吴文俊先生】 • 图灵机的停机问题：是否存在一个图灵机，他 可以回答其它图灵机是否停机【既算法是有界 的】 • 原则上是否存在一般数学问题的解题步骤的判 决问题【希尔波特第十问题变种】 • 图灵公理：凡是可计算的函数都可以用一台图 灵机来计算 清华大学 宋斌恒 4 NPC问题 • P－NP－NPC问题定义及其猜想：NPC是 一类不可以在多项式时间内计算的问 题。 • 如果在量子计算模型中上述问题又如 何？ 清华大学 宋斌恒 5 下面介绍计算机械化的进程 清华大学 宋斌恒 6 明代数学家程大位著《算法统 宗》中关于珠算的插图
机械式手动计算机 机械计算机 ·法国数学家、哲学家帕斯卡在1642年发 明了一种机械计算机,并与1649年取得 专利。帕斯卡的计算机采用一种齿轮系 统,其中一小轮转十个数字,下一个小 轮便转动一个数字,通过齿轮系的联 动,可以进行加法和减法的运算 清华大学宋域恒 请华大学宋恒 图灵 图灵机模型 大半个世纪以来,数学家、计算机 有限状态 控制器 念英国数学家Iuri 912-1954)而设立的图灵奖成为计 读写头 带 清华大学末斌恒 请华大学宋恒 图灵机模型 图灵机定义 图灵机模型用一个无限长的带子作为无限存储 图灵机是一个7元组(Q,T,6,q0,q1,q2, 它还有一个读写头,这个读写头能在带子上读 其中Q,∑,都是有穷集合并宜 写和移动:开始时,带子上只有输入串,其它地 1)Q是状态集 方都是空的当它需要保存信息时,读写头就把 2)∑是输入字母表不包括特殊空白符号 信息写在带子上为了读某个输入或写下的信 ·3)r是带字母表,其中:∈T,∑是的子 息,带子可能将读写头往回移动到这个信息所 在的地方这样读,写和移动,机器不停的计算 4)6:Q×r→Q×r×{LR}是转移函数 直到产生输出为止机器实现设置了两种状态 0∈Q是起始状态 接受或拒绝 6)q1∈Q是接受状 7)q2∈Q是拒绝状态,且q2≠q1 清华大学末破恒 请华大学宋
2 清华大学 宋斌恒 7 机械式手动计算机 清华大学 宋斌恒 8 机械计算机 • 法国数学家、哲学家帕斯卡在1642年发 明了一种机械计算机，并与1649年取得 专利。帕斯卡的计算机采用一种齿轮系 统，其中一小轮转十个数字，下一个小 轮便转动一个数字，通过齿轮系的联 动，可以进行加法和减法的运算. 清华大学 宋斌恒 9 图灵 • 大半个世纪以来，数学家、计算机 科学家提出了各种各样的计算模型 都被证明是同图灵机器等价的。这 一理论已被当成公理，它不仅是计 算机科学的基础，也是数学的基础 之一。为纪念英国数学家Turing (1912-1954) 而设立的图灵奖成为计 算机界的诺贝尔奖. 清华大学 宋斌恒 10 图灵机模型 清华大学 宋斌恒 11 图灵机模型 • 图灵机模型用一个无限长的带子作为无限存储 , 它还有一个读写头 ,这个读写头能在带子上读 , 写和移动 : 开始时 ,带子上只有输入串 ,其它地 方都是空的 .当它需要保存信息时 ,读写头就把 信息写在带子上 .为了读某个输入或写下的信 息 ,带子可能将读写头往回移动到这个信息所 在的地方 .这样读 ,写和移动 ,机器不停的计算 , 直到产生输出为止 .机器实现设置了两种状态 : 接受 或 拒绝 清华大学 宋斌恒 12 图灵机定义 • 一个图灵机是一个7元组(Q,∑,Γ,δ,q0,q1,q2), 其中Q,∑,Γ都是有穷集合,并且 • 1) Q 是状态集. • 2) ∑是输入字母表,不包括特殊空白符号︺. • 3) Γ 是带字母表,其中: ︺∈Γ,∑是Γ的子 集. • 4) δ: Q×Γ→Q×Γ×{L,R}是转移函数. • 5) q0∈Q是起始状态. • 6) q1∈Q是接受状态. • 7) q2∈Q是拒绝状态,且 q2≠q1
多带图灵机 非确定性的图灵机 ·在计算的任何时刻机器可以在多种可能 灵机相似,M 性中选择一种继续进行【永远选择正确 只是有多 的,可以理解为全部分支都计算完后选 个带子每 出正确的】它的计算是一课树,不同的分 个带子都 枝对应着机器不同的可能性如果某个计 有自己的 算分枝导致接受状态,则接受该输入.与多 读写头,用 带图灵机相同的是,它的计算能力与普通 于读和写 图灵机也是一样的当然他的计算速度就 不一样了 清华大学宋域恒 请华大学宋恒 现代计算机模型 随机存取机RAM CPU 类似现代计算机,有一个只读输入 运算器控制器出 只写输出带、指令计数器、内存储器 其零号寄存器用作累加器,内存不能 存储器 写,每个内存可以存放任意大的整数 有12条指令:load、 store、add、su mult、div、read、 write、jump、jgtz 外存设备 Izero、halt 清华大学末斌恒 请华大学宋恒 练习 随机存取存储程序机RASP ·利用RAM设计一个计算多项式函数求值 ·除了程序可以存储在存储器中并可以修 的程序:其中多项式为<a0al,an>,变 改,其它与RAM都一样 量为 ·考虑问题:程序是什么?输入是什么? 复杂度是多少? 清华大学末域恒 请华大学宋
3 清华大学 宋斌恒 13 多带图灵机, • 和普通图 灵机相似, 只是有多 个带子,每 个带子都 有自己的 读写头,用 于读和写. 如图 清华大学 宋斌恒 14 非确定性的图灵机 • 在计算的任何时刻,机器可以在多种可能 性中选择一种继续进行【永远选择正确 的，可以理解为全部分支都计算完后选 出正确的】.它的计算是一课树,不同的分 枝对应着机器不同的可能性.如果某个计 算分枝导致接受状态,则接受该输入.与多 带图灵机相同的是,它的计算能力与普通 图灵机也是一样的.当然他的计算速度就 不一样了。 清华大学 宋斌恒 15 现代计算机模型 清华大学 宋斌恒 16 随机存取机RAM • 类似现代计算机，有一个只读输入带、 只写输出带、指令计数器、内存储器、 其零号寄存器用作累加器，内存不能 写，每个内存可以存放任意大的整数。 有12条指令：load、store、add、sub、 mult、div、read、write、jump、jgtz、 jzero、halt。 清华大学 宋斌恒 17 练习 • 利用RAM设计一个计算多项式函数求值 的程序：其中多项式为<a0,a1,…,an>，变 量为x。 • 考虑问题：程序是什么？输入是什么？ 复杂度是多少？ 清华大学 宋斌恒 18 随机存取存储程序机RASP • 除了程序可以存储在存储器中并可以修 改，其它与RAM都一样
RAM、RASP复杂度耗费标准 图灵机模型与RAM模型计算能力 和复杂性关系 ·均匀耗费:不论计数器内整数多长,其 ·定理一、上述计算模型的计算能力等 读写、运算耗费均相等 价:既能够用图灵机计算的问题一定能 对数耗费:耗费与其二进制表示的位数 够用RAM计算,反之亦然。 成正比:既与数字大小的对数成正比 ·定理二、在对数耗费标准下、图灵机与 RAM的计算复杂度可在多项式时间内相 互归约。 清华大学宋域恒 请华大学宋恒 问题变换与复杂性归约 说明 利用变换和归约可以把一个问题的复杂 A∝nB:是指在完成问题A到B 性归结到另一个问题的复杂性 的转换过程中的转换过程需要Or(n) 问题A变换到问题B是指 将问题A的输入变换为问题B的适当输入 通常n表示问题A的规模,如果 求解问题B 把问题B的输出变换为问题A的正确解 r(m)是多项式,则称问题A可在多项 式时间内变换为问题B 清华大学末斌恒 请华大学宋恒 P、NP类定义 A Formal-language framework ·P={L是一个能够在多项式时间内被 形式化语言框架的一些概念简介 台确定性图灵机所接受的语言 Alphabet 2: is a finite set of symbols ·NP={LL是一个能够在多项式时间内被 一台非确定性图灵机所接受的语言} of symbols from 2. If 2=10, 11, then ·遗留概念说明 L=(10, 11, 101, 111, 1011,.., is the language of 语言 口 E is the empty string 语言与图灵机【算法与图灵机】 a2=E, 0, 1,00,01, 11,-.i is the set of all strings 为什么选择多项式 Every language is an element of x 清华大学末破恒 请华大学宋
4 清华大学 宋斌恒 19 RAM、RASP复杂度耗费标准 • 均匀耗费：不论计数器内整数多长，其 读写、运算耗费均相等 • 对数耗费：耗费与其二进制表示的位数 成正比：既与数字大小的对数成正比 清华大学 宋斌恒 20 图灵机模型与RAM模型计算能力 和复杂性关系 • 定理一、上述计算模型的计算能力等 价：既能够用图灵机计算的问题一定能 够用RAM计算，反之亦然。 • 定理二、在对数耗费标准下、图灵机与 RAM的计算复杂度可在多项式时间内相 互归约。 清华大学 宋斌恒 21 问题变换与复杂性归约 • 利用变换和归约可以把一个问题的复杂 性归结到另一个问题的复杂性 • 问题A变换到问题B是指： – 将问题A的输入变换为问题B的适当输入 – 求解问题B – 把问题B的输出变换为问题A的正确解 清华大学 宋斌恒 22 说明 A∝τ (n) B：是指在完成问题 A 到 B 的转换过程中的转换过程需要O(τ (n)) 时间。 通常 n 表示问题 A 的规模，如果 τ (n) 是多项式，则称问题 A 可在多项 式时间内变换为问题 B 清华大学 宋斌恒 23 P、NP类定义 • P＝{L|L是一个能够在多项式时间内被一 台确定性图灵机所接受的语言} • NP＝{L|L是一个能够在多项式时间内被 一台非确定性图灵机所接受的语言} • 遗留概念说明： – 语言 – 语言与图灵机【算法与图灵机】 – 为什么选择多项式 清华大学 宋斌恒 24 A 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}, then 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 Σ∗
Operations on language 多项式时间内可求解问题 Union and intersection: same as the set 多项式时间内可求解的问题的特点 perations 多项式时间可求解的问题被认为是易处理 Complement ofL:I=2'-L Concatenation of two language L, and L2 理由1:尽管θ(n10)算法被认为是不 L={x1x2:x∈L1,x2∈L2} 易处理的,但事实上还没有什么实际问题有 如此之高的多项式算法。 Closure or Kleene Star 经验证明一但一个问题有多项式解,那 L*=GULULZULU 么常常会有更加有效的解决方案 清华大学宋域恒 请华大学宋恒 理由2:在某一种计算模型下有多项式算法则 在另一种计算模型下亦有多项式算法 2抽象问题 例如:一个问题在串行随机存取机上有 多项式算法,则在图林机上亦有多项式算 抽象问题Q是集合I和S上的二元关系。其中 法,在并行机上亦如此。 理由3:多项式算法时间问题集合有非常好的 ·例如:①最短路径问题:问题实例(G, 封闭性质,它在加、乘、复合运算下都是 u、v):一个圆和其上两个顶点;问题解 封闭的 是(u~v)一个从u到v的由边相连的顶点 【本课程研究的算法大部分是多项式的,研 究的问题也是在多项式时间内可解的,对 ②查找最小值问题:问题实例 于不能在多项式时间内求解的问题该如何 a1,…,an>一个数组。解:数m。 处理?】 清华大学末斌恒 请华大学宋恒 判决问题 3.编码:抽象对象集合S的编码是: 抽象对象集合S的编码是 · Decision问题:如果I={0,1}或 E:S→∑*即把S中的对象e转化成一个二进 yes,no},则称问题是判决问 制(可以是多进制)的串。 题,下面我们只关心判决问题。 优化问题一般都可以转换成判决 构成,称其为具体问题。我们称 辈漆 问题。 在0(T(n))时间内解决了一个具体问 题,如果此问题i的长度|i是n,此算法可 在0(T(n))时间内求解此问题 一个抽象问题可以编码成具体问题。 清华大学末破恒 请华大学宋
5 清华大学 宋斌恒 25 Operations on language • Union and intersection: same as the set operations • Complement of L: • Concatenation of two language L1 and L2: • Closure or Kleene Star: – L*={ε}U L U L2 U L3 U… L = Σ − L * { : , } 1 2 1 1 2 L2 L = x x x ∈ L x ∈ 清华大学 宋斌恒 26 多项式时间内可求解问题 • 多项式时间内可求解的问题的特点 – 多项式时间可求解的问题被认为是易处理 的，有三条理由： 理由1：尽管Θ(n100)算法被认为是不 易处理的，但事实上还没有什么实际问题有 如此之高的多项式算法。 经验证明一但一个问题有多项式解，那 么常常会有更加有效的解决方案。 清华大学 宋斌恒 27 理由2：在某一种计算模型下有多项式算法则 在另一种计算模型下亦有多项式算法。 例如：一个问题在串行随机存取机上有 多项式算法，则在图林机上亦有多项式算 法，在并行机上亦如此。 理由3：多项式算法时间问题集合有非常好的 封闭性质，它在加、乘、复合运算下都是 封闭的 【本课程研究的算法大部分是多项式的，研 究的问题也是在多项式时间内可解的，对 于不能在多项式时间内求解的问题该如何 处理？】 清华大学 宋斌恒 28 2.抽象问题： 抽象问题Q是集合I和S上的二元关系。其中 I是问题实例集合，S是问题解集合。 • 例如：①最短路径问题：问题实例（G， u、v):一个圆和其上两个顶点；问题解 是（u～v)一个从u到v的由边相连的顶点 集。 ②查找最小值问题：问题实例： ＜a1,…,an＞一个数组。解:数m。 清华大学 宋斌恒 29 判决问题 • Decision问题：如果I＝｛0，1｝或 ｛yes,no｝，则称问题是判决问 题，下面我们只关心判决问题。 优化问题一般都可以转换成判决 问题。 清华大学 宋斌恒 30 3.编码：抽象对象集合S的编码是： 抽象对象集合S的编码是： E：S→∑＊即把S中的对象e转化成一个二进 制（可以是多进制）的串。 如果一个问题的实例是由二进制串集 构成，称其为具体问题。我们称一个算法 在O（T（n)）时间内解决了一个具体问 题，如果此问题i的长度|i|是n，此算法可 在O（T（n)）时间内求解此问题。 一个抽象问题可以编码成具体问题