1 清华大学 宋斌恒 1 NP完全性理论介绍 清华大学 宋斌恒 清华大学 宋斌恒 2 内容提要 ? 计算模型与计算复杂度关系 ? 问题分类：【 P】与【 NP】类 ?NP－难【 hard】问题， NP完全集 ? 第一个 NPC问题和 NPC问题集 ? 如何证明一个问题是 NPC问题 清华大学 宋斌恒 3 引言 ? 脑力劳动机械化【吴文俊先生】 ? 图灵机的停机问题：是否存在一个图灵机，他 可以回答其它图灵机是否停机【既算法是有界 的】 ? 原则上是否存在一般数学问题的解题步骤的判 决问题【希尔波特第十问题变种】 ? 图灵公理：凡是可计算的函数都可以用一台图 灵机来计算 清华大学 宋斌恒 4 NPC问题 ?P－ NP－ NPC问题定义及其猜想： NPC是 一类不可以在多项式时间内计算的问 题。 ? 如果在量子计算模型中上述问题又如 何？ 清华大学 宋斌恒 5 下面介绍计算机械化的进程 清华大学 宋斌恒 6 明代数学家程大位著《算法统 宗》中关于珠算的插图 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 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都一样。 4 清华大学 宋斌恒 19 RAM、 RASP复杂度耗费标准 ? 均匀耗费：不论计数器内整数多长，其 读写、运算耗费均相等 ? 对数耗费：耗费与其二进制表示的位数 成正比：既与数字大小的对数成正比 清华大学 宋斌恒 20 图灵机模型与 RAM模型计算能力 和复杂性关系 ? 定理一、上述计算模型的计算能力等 价：既能够用图灵机计算的问题一定能 够用 RAM计算，反之亦然。 ? 定理二、在对数耗费标准下、图灵机与 RAM的计算复杂度可在多项式时间内相 互归约。 清华大学 宋斌恒 21 问题变换与复杂性归约 ? 利用变换和归约可以把一个问题的复杂 性归结到另一个问题的复杂性 ? 问题 A变换到问题 B是指： – 将问题 A的输入变换为问题 B的适当输入 – 求解问题 B – 把问题 B的输出变换为问题 A的正确解 清华大学 宋斌恒 22 说明 A )(nτ ∝ B：是指在完成问题 A 到 B 的转换过程中的转换过程需要 ))(( nO τ 时间。 通常 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, nullεis the empty string. nullΣ * ={ε,0,1,00,01,11,…} is the set of all strings – Every language is an element of Σ ? . 5 清华大学 宋斌恒 25 Operations on language ? Union and intersection: same as the set operations ? Complement of L: ? Concatenation of two language L 1 and L 2 : ? Closure or Kleene Star: –L*={ε}U L U L 2 U L 3 U… LL ?Σ= * },:{ 221121 LxLxxxL ∈∈= 清华大学 宋斌恒 26 多项式时间内可求解问题 ? 多项式时间内可求解的问题的特点 – 多项式时间可求解的问题被认为是易处理 的，有三条理由： 理由1：尽管 Θ(n 100 )算法被认为是不 易处理的，但事实上还没有什么实际问题有 如此之高的多项式算法。 经验证明一但一个问题有多项式解，那 么常常会有更加有效的解决方案。 清华大学 宋斌恒 27 理由 2：在某一种计算模型下有多项式算法则 在另一种计算模型下亦有多项式算法。 例如：一个问题在串行随机存取机上有 多项式算法，则在图林机上亦有多项式算 法，在并行机上亦如此。 理由 3：多项式算法时间问题集合有非常好的 封闭性质，它在加、乘、复合运算下都是 封闭的 【 本课程研究的算法大部分是多项式的，研 究的问题也是在多项式时间内可解的， 对 于不能在多项式时间内求解的问题该如何 处理？】 清华大学 宋斌恒 28 2.抽象问题： 抽象问题 Q是集合 I和 S上的二元关系。其中 I是问题实例集合， S是问题解集合。 ? 例如：①最短路径问题：问题实例（G， u、v):一个圆和其上两个顶点；问题解 是（u～v)一个从u到v的由边相连的顶点 集。 ②查找最小值问题：问题实例： ＜a 1 ,…,a n ＞一个数组。解:数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)）时间内求解此问题。 一个抽象问题可以编码成具体问题。 6 清华大学 宋斌恒 31 Problem 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={x∈{0,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)=0 清华大学 宋斌恒 32 Polynomial time ? We say that a language is accepted in polynomial time by an algorithm A if A accepts every binary string in L in polynomial time[无法保证非 L中的语言在多项式时间内 被拒绝 ] ? 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 清华大学 宋斌恒 33 class P的另一个等价定义 ?P={L ? {0,1}*: there exists an algorithm A that decides L in polynomial time} 清华大学 宋斌恒 34 Polynomial 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. 清华大学 宋斌恒 35 Language defined by verification ? L={x in {0,1} * : there exists y in {0,1} * such that A(x,y)=1} 清华大学 宋斌恒 36 NP的一个等价定义 ? A language L belongs to NP if and only if there exists a two-input polynomial-time algorithm A and a constant c such that ? L={x in {0,1} * : there exists y in {0,1} * with |y|=O(|x| c ) such that A(x,y)=1} ? We say that algorithm A verifies language L in polynomial time. 7 清华大学 宋斌恒 37 NP两种定义是等价的 ? 用非确定性图灵机和验证算法给 NP类的 定义是等价的 清华大学 宋斌恒 38 关于团问题属于 NP的两种表述 ? 团：给定无向图和整数 k，确定是否存在一个 包含 k顶点的完全子图【团】【 Clique】。 ? 非确定图灵机算法：一个转移函数：给定 k， 可以不确定地转移到任意一个包含 k个顶点的 子图，然后确认该子图是否是团。其复杂度为 多项式。 ? 验证算法：给定一个 k阶子图，验证它是否为 团。 清华大学 宋斌恒 39 co-NP ? Complexity Class co-NP={L: complement of L in NP} ? 余集 清华大学 宋斌恒 40 P is a subset of NP P=NP=co-NP NP=co-NP P Co-NP NP ∩co-NP NP =P 清华大学 宋斌恒 41 The most possible cases Co-NP NP ∩co-NP NP P 清华大学 宋斌恒 42 NP-Complete and reducibility ? The “hardest” language in NP, with polynomial-time reducibility. ? 多项式约简： we call L 1 is polynomial- time reducible to L 2 , denoted as L 1 ≤ p L 2 , if there exists a polynomial-time function f: {0,1}* ? {0,1}* such that for all x in {0,1}*, x in L 1 iff f(x) in L 2 . 8 清华大学 宋斌恒 43 Class NPC ?NPC={L in NP: L’ ≤ p L for every L’ in NP} ?NP-Hard: if L’≤ p L for every L’ in NP, we call L is NP-hard ? Theorem34.4 If any one of the NPC problem is belong to P, then P=NP 清华大学 宋斌恒 44 Existence of NPC problem ? Circuit satisfiability:【芯片满足性问题】 – Input n Boolean variables after a sequence of Boolean operations it outputs a value from {0,1}, if there exists a input such that its output is one we say the circuit is satisfiable. ? Circuit-SAT={<C>:C is satisfiable boolean combinational circuit} ? Theorem Circuit-SAT is belong to NPC 清华大学 宋斌恒 45 NP-completeness proofs ? 证明 circuit-satisfiability 问题是 NPC问 题，依赖我们是否能够证明对于所有属 于 NP的语言 L都有： L ≤ p Circuit-SAT, 其 证明超出了我们的课程的内容。 ? 那么对于一般问题的 NP完全是如何证明 的？这里我们把其中的过程做个介绍： 清华大学 宋斌恒 46 Lemma34.8 ? 如果 L是一个语言，如果存在一个 L’属于 NPC，且满足 L’ ≤ p L，则 L是 NP－难的 （ NP-hard） ,如果进一步有 L是 NP则 L属 于 NPC。 ? 证明：利用定义可以证明 清华大学 宋斌恒 47 一般证明语言 L是 NPC的步骤 ? 证明 L属于 NP ? 选取一个已知的 NPC语言 L’ ? 找到一个算法 f使得 f将 L’的每一个 属于 {0,1}*实例 x映射到 L的实例 f(x). ? 证明函数 f满足 x 属于 L’ 等价于 f(x) 属于 L对于所有 属于 {0,1}*的 x都成立 ? 证明计算 f的算法是多项式的 清华大学 宋斌恒 48 Formula satisfiability ? Language SAT is defined as: –SAT的实例是一个逻辑公式 φ，其构成如下 1. n布尔变量： x 1 ,x 2 ,x 3 ,…x n . 2. m布尔运算符： and、 or、 not、 implication、 if and only if(?,∧,∨,→,?)和 3. 括号（没有多余括号） ? 我们可以证明 SAT属于 NPC【 Cook定 理】 9 清华大学 宋斌恒 49 证明： SAT属于 NP ? 只需要证明把一个实例代入公式进行布 尔运算即可，其复杂度是多项式没有任 何问题！ ? 【有优先级的公式计算问题是多项式 的】 ?SAT是 NP－ hard的：我们可以把 Circuit－ Satisfiable问题约简为 SAT问题，而后证 明约简过程是多项式的和充要的 清华大学 宋斌恒 50 3－ CNF－ SAT ? Formula in conjunctive normal form: ?∧∨→? ? f= (clause 1 ) ∧ (clause 2 ) ∧ …∧ (clause k ) – Where clauses contains only ?, ∨ and variables(variables and ?variables called literials) ? 3-conjunctive-normal-form: every clause contains exactly 3 literals. 清华大学 宋斌恒 51 3-CNF-SAT是 NP完全的 ? 验证是多项式的，没有问题 清华大学 宋斌恒 52 The Clique Problem ? Clique Problem（团）： A clique is a complete subgraph of G. Here above G is a graph. ? CLIQUE={<G,k>:G is a graph with a clique of size k} ? Theorem: Clique problem is NP-complete 清华大学 宋斌恒 53 Vertex-Cover problem ? A vertex-cover of an undirected graph G=(V,E) is a subset V’ contains in V such that if (u,v) in E, then u in V’ or v in V’(or both). ? A vertex-cover problem is to find a vertex cover of minimum size in a given graph ? Decision problem: VERTEX-COVER={<G,k>:G has a vertex cover of size k} ? VERTEX-COVER 属于 NPC 清华大学 宋斌恒 54 Hamiltonian-cycle ? A Hamiltonian cycle is a sequence of V such that it runs all the vertices once exactly excepting the start and end vertex is the same one(it runs two times), and the running sequence is a path of the graph. ? HAM-CYCLE is belong to NPC 10 清华大学 宋斌恒 55 Traveling-salesman Problem ? 旅行商问题：旅行商必须访问所有 n个城 市，而每两个城市之间的的行走费用不 同，求一条费用最小的路径 ? TSP is NP-complete 清华大学 宋斌恒 56 The subset-sum problem ?In the subset-sum problem, we are given a finite set S subset of N, and a target t in N, we ask whether there is a subset S’ subset of S whose elements sum to t. ? SUBSET-SUM={<S,t>,there exists a subset S’ of S such that t = Σ s∈ S’ s} ? SUBSET-SUM is NP-complete. 清华大学 宋斌恒 57 目前对 NPC问题的处理 ? 由于没有迹象表明 NPC问题可以有多项 式时间的算法，当然也没有证明它没 有。目前人们对于 NPC问题主要是采取 近似计算方法来解决这类问题， 清华大学 宋斌恒 58 Approximation Algorithms ? Optimization problem has a minimum or maximum value(we assume it is positive), we denote as C ? Approximation algorithm cannot get the optimal solution hence it computes an approximate value, called C*, ? Performance ratios for approximation algorithms: ρ(n) satisfies ?Max{C/C*, C*/C}≤ ρ(n) ? We call the algorithm is ρ(n)-approximation algorithm 清华大学 宋斌恒 59 Approximation scheme ? An approximation scheme for an optimization problem is an approximation algorithm that takes as input not only an instance of the problem, but also a value ε >0 such that for any fixed ε, the scheme is a (1+ε)-approximation algorithm ? Polynomial time approximation scheme ? Fully polynomial time approximation scheme 清华大学 宋斌恒 60