计算复杂性的概念.ppt

1.4 计算复杂性的概念 定义1.3 所谓组合(最)优化(Combinatorial Optimization)又称离散优化 （Discrete Optimization），它是通过数学方法去寻找离散事件的最 优编排、分组、次序或筛选等. 这类问题可用数学模型描述为： 优化问题三要素: (Min,f,F)或(Max,f,F) 其中D表示有限个点组成的集合(定义域) , f为目标函数,F=x|xD, g(x)0为可行域 1.4.1 组合优化 定义 1 1.4 计算复杂性的概念 1.4.1 组合优化 例 例1.7 0-1背包问题(knapsack problem) 给定n个容积分别为ai，价值分别为ci的物品.设有一个容积为b的背包，如何 以最大的价值装包？用数学规划模型表示为： D= 0,1n 例1.10 装箱问题(Bin Packing) 以尺寸为1的箱子装进给定的n个尺寸不超过1的物品，如何使所 用的箱子个数最少? 2 1.4 计算复杂性的概念 1.4.1 组合优化 例 例1.9 整数线性规划(Integer Linear Programming) (IP) . 我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数(或 有理数). 许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然语 言描述简洁 3 1.4 计算复杂性的概念 1.4.2 多项式时间算法 对于组合优化问题，我们关心的一般不是最优 解的存在性和唯一性，而是如何找到有效的算 法求得一个最优解. 那么如何衡量算法的优劣 、有效与无效呢？ 完全枚举法可以求得最优解,但枚举时间有时不可能接受 ATSP: (n-1)!枚举(TOUR,周游或环游) 设计算机每秒进行100亿次枚举,需 30! / 10e+10 2.65e+22 (秒) 即 2.65e+22 / (365*24*60*60) 8.4e+13 (年) 4 1.4 计算复杂性的概念 1.4.2 多项式时间算法 构造算法的目的是能够解决问题（或至少是问题某个 子类）的所有实例而不单单是某一个实例 问题（Problem）是需要回答的一般性提问，通常含有若干个满 足一定条件的参数. 问题通过下面的描述给定：（1）描述所有 参数的特性，（2）描述答案所满足的条件. 问题中的参数赋予了具体值的例子称为实例(instance). 衡量一个算法的好坏通常是用算法中的加、减、乘、 除和比较等基本运算的总次数（计算时间）C（I）同 实例I在计算机计算时的二进制输入数据(输入规模/长 度d（I）)的大小关系来度量. 计算模型 C(I) = f(d(I) : 该函数关系称为算法的计算复杂性（度） 5 1.4 计算复杂性的概念 1.4.2 多项式时间算法 对于一个正整数x，二进制表示是以 如ATSP:二进制输入长度总量不超过 (不考虑正负号、分隔符等) 的系数来表示，其中， x的二进制数的位数不超过 假设每一个数据(距离)的绝对值都有上界K 输入长度是n的多项式函数 所以网络优化中常用n,m等表示输入规模 6 1.4 计算复杂性的概念 1.4.2 多项式时间算法 例 构造算法将n个自然数从小到大排列起来 算法 输入自然数a(1),a(2),a(n). for (i=1;ia(j) k=a(i);a(i)=a(j);a(j)=k; 即该算法的计算复杂性（度）为O(n2) 基本运算的总次数(最坏情形）：2n(n-1)=O(n2) 比较： （n-1)+(n-2)+1=n(n-1)/2 赋值： 3(n-1)+(n-2)+1=3n(n-1)/2 7 1.4 计算复杂性的概念 定义1.4 假设问题和解决该问题的一个算法已经给定，若存在g(x)为多项式 函数且对该问题任意的一个实例I，使得计算时间 成立，则称该算法为解决该问题的多项式(时间)算法(Polynomial time algorithm). 当不存在多项式函数g(x)使得上式成立时，称相应的算法是非多项式时 间算法, 或指数(时间)算法(Exponential time algorithm) 输入规模增大时，多项式时间算法的基本计算总次 数的增加速度相对较慢. 1.4.2 多项式时间算法 注：上面定义中，要求对该问题的任意一个实例均成立 ， 这种分析方法称为最坏性能分析（Worst-Case Analysis） 8 1.4 计算复杂性的概念 1.4.2 多项式时间算法 近似值计算机提速10倍 n10100100010121013 nlogn3366499660.9e110.87e12 n21001041061063.16e6 n310001061091042.15e4 108n41012101610201018 2n10241.27e30 1.05e301 4043 10n1010101001010001213 nlogn20791.93e13 7.89e297995 n!3628800101584e25671415 9 1.4 计算复杂性的概念 1.4.2 多项式时间算法 算法复杂性研究中:常将算法的计算时间表示为： 问题中的简单而典型的参数(如网络优化中n,m), 以及 问题中出现的数值(如弧上的权)的最大值(按绝对值)K 等自变量的函数关系 如果算法运行时间的上界是m,n和K的多项式函数，则称相应的算法为伪 多项式（Pseudopolynomial）（时间）算法，或拟多项式（时间）算法. 实际问题的输入规模/长度一定是m,n和logK的一个多项式函数. 所以： 多项式算法等价于其运行时间的上界是m,n和logK的多项式函数. 特别地, 如果运行时间的上界是m,n的多项式函数（即该多项式函数不包 含logK）, 则称相应的算法为强多项式(Strongly Polynomial)时间算法 . 一般来说，伪多项式算法并不是多项式算法. 10 1.4 计算复杂性的概念 TSP等许多问题至今没有找到多项式时间算法,但尚未证 明其不存在 定义1.5 对于给定的一个优化问题，若存在一个求解该问 题最优解的多项式时间算法，则称给定的优化问题是多 项式可解问题，或简称多项式问题，所有多项式问题集 记为P(Polynomial). 同样道理, 可以定义强多项式问题,伪多项式问题等. TSP是否存在多项式时间算法? - 这是 21世纪数学和计算机科学的挑战性问题之一 1.4.3 多项式问题 11 网 络 优 化 第 1 章 概 论 (第2讲) Network Optimization 清华大学数学科学系 谢金星 办公室：理科楼2206# （电话 Email: /jxie/courses/netopt 1.5 NP,NPC和NP-hard概念 (计算复杂性理论） 12 运筹学的ABC - A2B2C2 （至少是组合优化、理论计算机科学的ABC） q Approximation Algorithm (近似算法)；Heuristic q Branch and Bound （分枝定界） q Computational Complexity （计算复杂性） 口莫开，开口常说错。 理论在监督， 众目睽睽难逃脱。 计算复杂性理论的“Bible” Garey M R.and Johnson.D S, Computers and intractability : a guide to the theory of NP-completeness. San Francisco :.W.H. Freeman and Co., 1979 (中译本: 计算机和难解性：NP-C理论导论. 张立昂等译, 科学出版社，1987) 13 1.5.1 问题、实例与输入规模 评价一个算法的依据是该算法在最坏实例下的计算时间与 实例输入规模的关系： 问题实例 TSP 问题中各参数:100个城市，城市间距离 已知. 背包问题问题中各参数: 4个物品，大小分别为4,3,2,2. 价 值分别为8,7,5,7. 包的大小为6. 整数线性规划问题中的n,A,b,c已知. 比多项式问题类可能更广泛的一个问题类是非确定多项式 (Nondeterministic Polynomial，简记 NP ) 问题类 存在多项式算法的问题集合：多项式问题类（P） 存在多项式函数 g(x) 满足上式时，算法为多项式算法 NP 类是通过判定问题引入的。 14 对任何一个优化问题， 可以考虑其三种形式： 最优化形式（原形：最优解） 计值形式（最优值） 判定形式（上界） 定义1.6 如果一个问题的每一个实例只有“是”或“否”两 种答案，则称这个问题为判定问题(Decision / recognition / feasibility problem). 称有肯定答案的实 例为“是”实例(yes-instance). 称答案为“否”的实例为 “否”实例或非“是”实例(no-instance). 1.5.2 判定问题 - 定义 例1.13 线性规划问题(LP)的判定形式LP判定问题： 给定一个实数值z，(LP)是否有可行解使其目标值不超过z？ 即：给定z，是否有 ? 难度降低 就有效算法的存在性而言，通常认为三种形式等价！ 15 文字集 例1.15 适定性问题(Satisfiability problem) 在逻辑运算中，布尔变量x的取值只有两个： “真”(1)和“假”(0)，逻辑运算有“或（+ ）”，“与（）”和“非（）. 1.5.2 判定问题 - 例 存在真值分配的表达式称为适定的(可满足的) + 000 011 101 111 000 010 100 111 01 10 文字集的任意一个子集中各元素（布尔变量） 的“或”运算组成一个句子,多个句子的“与 ”运算组成一个表达式，如 适定性问题：给定布尔表达式 ， （SAT）是适定的吗？ 16 1.5.2 判定问题 - 例 例1.16 三精确覆盖(3-Exact Covering：X3C) 已知 的n个子集构成的子集族 ， 其中每个子集包含S中三个元素，F中是否存在m个子集 ， 使得 ？ 若m个子集满足上式，则称这m个子集精确覆盖S. 17 定义1.7 若存在一个多项式函数g(x)和一个验证算法H，对一类 判定问题A的任何一个“是” 实例I，都存在一个字符串S是I 的可行解，满足其输入长度d(S)不超过g(d(I)，其中d(I)为I的 输入长度，且算法H验证S为实例I的可行解的计算时间f(H)不 超过g(d(I)，则称判定问题A是非确定多项式的。 考虑将求解判定问题的算法分为两个阶段： （1）猜测阶段：求出或猜测该问题的一个解 （2）检查或验证阶段：一旦解已经选定，将猜测的解作为输 入，验证此解是否为该实例“是”的回答. 我们称实例“是” 回答的解为实例的可行解，否则称为不可行解. 所有非确定多项式问题的集合用NP表示. 1.5.3 非确定多项式问题类(NP) 定义 构造字符串（解）的过程及验证算法H一起构成一个算法，称 为非确定多项式（时间）算法。 18 所以，可以从讨论基本可行解的性质入手 整系数问题等价于有理系数问题 1.5.3 非确定多项式问题类(NP) 例 例1.17 整系数（或有理系数）的LP判定问题问题 属于NP. 其实， ， LPP，所以LPNP. 下面考虑通过定义来说明 LPNP 分析与思考： (注意：第1次印刷版教材上的证明可能有漏洞) （不）等式组有可行解，等价于它有基本可行解 LP判定问题等价于验证如下（不）等式组的可行解问题 因此可以不考虑目标函数问题，仍记为 19 1.5.3 非确定多项式问题类(NP) 例 引理1.1 LP问题的约束的基本可行解的各分量值有界，其二进 制字符串表达式的输入长度不超过 例1.17 整系数（或有理系数）的LP判定问题问题 属于NP. （续） 输入长度不超过 又 ， ， ，分量值不超过 20 验证时最多需 (m+1)n个乘，(m+1)(n-1)个加或减，n+m+1个比 较，共计 LP实例的输入长度d(I)满足 1.5.3 非确定多项式问题类(NP) 例 LP的一个基本可行解的输入长度不超过 例1.17 整系数（或有理系数）的LP判定问题问题 属于NP. （续） 对LP判定问题的一个“是”实例，上述约束组（等式和不等式 组）一定存在一个基本可行解. 当给定一个基本可行解x，只要 验证是否满足 ？ 取多项式函数g(x)=2x2，则满足定义，所以LPNP. 21 F中m个元素 是S的一个精确三覆盖的充分必要条件为： 相应的m个向量满足 集合S中共有3m个元素，子集族F中的每个子集合对应一个3m维向量：向量 的3m个分量对应3m个元素，元素包含在对应子集中的分量为1，余下的为0. 例如： S= ，F中的一个元素 ，对应向量为 = (1,1,0,0,0,1)，表示为一个字符串(110001). 1.5.3 非确定多项式问题类(NP) 例 按字符串向量问题，精确三覆盖 “是”实例的任何一个解可以用长度为3m2 的字符表示. 验证是否可行解的算法最多需3m2 个加法和3m个比较，算法的计算时间为 3m2 +3m. 例1.19 三精确覆盖属于NP 三精确覆盖问题任何一个实例的输入长度d(I)3m. 选g(x)= x2 /3+x ，则定义条件满足，所以三精确覆盖属于NP. 22 1.5.3 非确定多项式问题类(NP) 问题A2的难度不低于问题A1 定义1.8 给定问题A1和A2，若存在一个多项式算法满足： 对A1的任何一个实例I1，算法将实例I1的输入转换为A2的一 个实例I2的输入； 这种转换过程使得实例I1和I2的解一一对应，即将实例I1的 一个解x1的输入转换为实例I2的一个解x2的输入，且x1为I1的“ 是”答案 x2是I2的一个“是”答案； 则称A1问题多项式转换为A2问题，算法称为问题A1到问题A2 的一个多项式转换（算法）(Transformation). 常用的研究方法 - 多项式转换(变换)、多项式归约(归结) 若A1多项式转换为A2，且A2P，则A1P 若A1多项式转换为A2，且A2NP，则A1NP 多项式转换(定义) 23 进一步，该映射可以在SAT实例的输入长度 m n 的多项式时间内完成 SAT的一个实例是由 n 个逻辑变量和 m 个句子组成，输入长度是 m n. 1.5.3 非确定多项式问题类(NP) 多项式转换 等价于一个整数（0-1）线性规划问题（目标可以任意）。 例1.20 适定性问题多项式转换为整数（0-1）线性规划问题. 将 “真”对应“1”，“假”对应“0”，令逻辑变量 x 对应整数0或1， 对应1-x.含 n个变量的句子 (j=1,2,.,m) 为“真”，对应下列不等式组有可行解： 适定性问题多项式转换为整数（0-1）线性规划（判定）问题 24 进一步，该映射可以在 X3C 实例的输入长度的多项式时间内完成 特殊0-1背包判定问题（本书后面简称0-1背包判定问题）: 对给定的整数 和b，是否存在1,2,.,n的子集B，使得 ? 例1.21 三精确覆盖多项式转换为0-1背包判定问题 1.5.3 非确定多项式问题类(NP) 多项式转换 所以，三精确覆盖问题多项式转换为0-1背包判定问题 三精确覆盖实例的一个解一一对应背包问题实例的一个解： 假设存在B1,2,.,n，使得 . 由|B|不超过n，知左边和式中 （n+1)同次幂项的系数和不超过n（无进位）；又由b的每个幂次项系 数为1,知左边和式中n+1的每个次幂项系数恰好为1. |jB 得S 的一个三精确覆盖 25 1.5.4 NP完全问题类(NPC) - 定义1.9 已知判定问题A1和A2，若存在多项式函数 和 ，使得对A1的任何实例I，在多项式时间内构造A2的一个实例 ，其输入长度不超过 ，并对A2的任何一个算法H2 ，都存在问题A1的一个算法H1，使得H1算法调用H2算法且使 得计算时间 ， 其中fH1(x)和fH2(x)分别表示算法H1和H2的计算时间与实例输 入长度x之间的关系，则称问题A1多项式归约为问题A2. 根据A2的算法H2， 构造A1的算法H1的过程，即映射 ：H2 H1 称为从A1到A2的一个多项式归约(reduction). 多项式归约(定义) 26 问题A2的难度不低于问题A1 (注：第1次印刷版有误) 若A1多项式归约为A2，且A2P，则A1P 若A1多项式归约为A2，且A2NP，则A1NP 若A1多项式归约为A2，则当把H1对H2的一次调用当成一次基本 运算时， H1是A1的多项式算法。 1.5.4 NP完全问题类(NPC) - 多项式归约 多项式转换是多项式归约的特例 归约映射可以如下构造： H1：STEP1 用多项式转换将A1的实例转换为A2的实例 STEP2 用H2算法求解A2的实例 即多项式转换可以认为是只允许调用一次H2的多项式归约 27 1.5.4 NP完全问题类 (NPC) - 多项项式归约归约 （例） 例1.22 适定问题问题 多项项式归约为归约为 三精确覆盖问题问题 （证明较繁，略）课后自己看书体会证明技巧 28 定义义1.10 （1）对对于判定问题问题 A，若ANP且NP中的任何一个问问 题题可在多项项式时间时间 内归约为归约为 A，则则称A为为NP完全问题问题 (NP- Complete或NPC).可以表示为为ANPC. NPC和NP-hard两者的区别是: 验证一个问题A是否为NP-hard 无须判断A是否属于NP. 根据定义可知NPCNPH. 当已知一个问题属于NPC或NPH时，如果再遇到一个新问题： （1）若已知问题多项式归约为新问题，则新问题属于NPH; 1.5.4 NP完全问题类(NPC) 定 义 （2）对对于判定问题问题 A，若NP中的任何一个问题问题 可在多项项式时时 间归约为间归约为 判定问题问题 A，则则称A为为NP困难问题难问题 (NP-hard 或NPH) .可以表示为为ANPH. （2）若还可以验证新问题属于NP，则新问题属于NPC. 29 1.5.4 NP完全问题类(NPC) 证明 例1.23 (Cook定理，1971）SATNPC. 前面已经证明SATNP，所以尚需证明： 任何一个NP问题可以多项式归约为SAT 计算复杂性理论的奠基性工作之一：第一个被证明的NPC问题 ！是证明许多其他NPC问题的出发点 基本思想： 若ANP，则A存在非多项式时间算法（猜测解、验证解）。 对猜测解、验证解的过程进行分析，构造一个SAT问题！ （证明细节较繁，略） 30 1.5.4 NP完全问题类(NPC) 证明（例） 例1.24 整数线线性规规划（ILP）的判定问题问题 属于NPC 例1.20已证明适定问题多项式转换为0-1线性规划(ZOLP)的 判定问题 ZOLP判定问题属于NPH 与线性规划的判定问题属于NP的证明类似，可以证明： 整数线性规划的判定问题属于NP 引理如果ILP有可行解，则它有一个可行解 推论： ZOLP多项式等价于ILP；ILP的判定问题问题 属于NPC 易知：ZOLP的判定问题属于NP ZOLP判定问题属于 NPC 31 1.5.4 NP完全问题类(NPC) 证明（例 ） 例1.25 三精确覆盖（X3C）属于NPC. SAT多项项式归约为归约为 X3C (例1.22) X3CNP （例1.19） X3C NPC 例1.26 （特殊）（0-1）背包判定问题属于NPC. X3C多项项式变换为为背包判定问题 （例1.21） 背包判定问题NP （易证） 背包判定问 题 NPC 32 1.5.4 NP完全问题类(NPC) 证明（例） 例1.27 （集合）划分（PARTITION）问题是NPC. PARTITION问题：给定整数 ，是否存在 1,2,.,n的一个子集S，使得 ？ 要证明PARTITIONNPC，尚需证明： 这是（特殊）（0-1）背包判定问题的一个特殊情况，包的容 积 背包判定问题NP PARTITIONNP 所有NP问题多项式转换/归约为集合划分问题，或： 某个NPC问题多项式转换/归约为集合划分问题 可以证明：背包问题多项式转换为集合划分问题 33 观察： 1.5.4 NP完全问题类(NPC) 证明（例） 例1.27 PARTITION问题是NPC. （续） 这个映射满足“转换”定义的性质 - 转换的多项式性 证明：背包问题多项式转换为集合划分问题 给定0-1背包判定问题的任何一个实例 构造集合划分问题的实例 其中 这个映射满足“转换”定义的性质 - 解的一一对应 性 34 1.5.4 NP完全问题类(NPC) 证明（例） 例1.27 PARTITION问题是NPC. （续） (充分性)若存在1,2,.,n+2的一个子集S 使得 由于 ，因此S含且只含n+1，n+2之一 存在1,2,.,n的子集S，使得 的充分必要条件是 存在1,2,.,n+2的一个子集S使得 . (必要性)若存在1,2,.,n的子集S，使得 ， 则存在1,2,.,n+2的一个子集S=S n+2使得 . 于是存在1,2,.,n的子集S，使得 即 35 1.5.4 NP完全问题类(NPC) 证明（例 ） 易证：装箱判定问题属于NP易证. 例1.28 装箱(BP)判定问题是NPC. (注：第1次印刷版有漏洞) 给定正整数K及n个物品，尺寸为 (正整数)， 是否能在K个尺寸为B (正整数)的箱子中装入这n个物品？ 要证明BPNPC，可将划分问题多项式转换为BP 给定正整数 ,构造BP问题:K=2， ， 这一过程可以在多项式时间内完成 存在1,2,.,n的子集S，使得 的充分必要条件是 在K=2个尺寸为B 的箱子中可以装入这n个物品 所以BPNPC （思考：正整数集合划分问题NPC） 36 1.5.4 NP完全问题类(NPC) 补充说明: 算法复杂性研究中:常将算法的计算时间表示为： 问题中的简单而典型的参数(如网络优化中n,m), 以及 问题中出现的数值(如弧上的权)的最大值(按绝对值)K， 等自变量的函数关系 实际问题的输入规模/长度一定是m,n和logK的一个多项式函数. 所以, 如果一个算法是多项式时间算法, 则运行时间的上界一 定也是m,n和logK的多项式函数. 特别地, 如果运行时间C(I)的上界是m,n的多项式函数（即该多 项式函数不包含logK）, 则称相应的算法为强多项式（ Strongly Polynomial）时间算法，简称强多项式算法. 强多项式算法/问题 存在强多项式算法的问题称为强多项式问题. 37 1.5.4 NP完全问题类(NPC