计算复杂性的概念.ppt

1,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 组合优化 定义,2,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的物品，如何使所用的箱子个数最少?,3,1.4 计算复杂性的概念,1.4.1 组合优化 例,例1.9 整数线性规划(Integer Linear Programming),(IP).,我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数(或有理数).许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然语言描述简洁,4,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(年),5,1.4 计算复杂性的概念,1.4.2 多项式时间算法,构造算法的目的是能够解决问题（或至少是问题某个子类）的所有实例而不单单是某一个实例,问题（Problem）是需要回答的一般性提问，通常含有若干个满足一定条件的参数.问题通过下面的描述给定：（1）描述所有参数的特性，（2）描述答案所满足的条件.,问题中的参数赋予了具体值的例子称为实例(instance).,衡量一个算法的好坏通常是用算法中的加、减、乘、除和比较等基本运算的总次数（计算时间）C（I）同实例I在计算机计算时的二进制输入数据(输入规模/长度d（I）)的大小关系来度量.计算模型,C(I)=f(d(I):该函数关系称为算法的计算复杂性（度）,6,1.4 计算复杂性的概念,1.4.2 多项式时间算法,对于一个正整数x，二进制表示是以,如ATSP:二进制输入长度总量不超过(不考虑正负号、分隔符等),的系数来表示，其中，,x的二进制数的位数不超过,假设每一个数据(距离)的绝对值都有上界K,输入长度是n的多项式函数所以网络优化中常用n,m等表示输入规模,7,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,8,1.4 计算复杂性的概念,定义1.4 假设问题和解决该问题的一个算法已经给定，若存在g(x)为多项式函数且对该问题任意的一个实例I，使得计算时间,成立，则称该算法为解决该问题的多项式(时间)算法(Polynomial time algorithm).当不存在多项式函数g(x)使得上式成立时，称相应的算法是非多项式时间算法,或指数(时间)算法(Exponential time algorithm),输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢.,1.4.2 多项式时间算法,注：上面定义中，要求对该问题的任意一个实例均成立，这种分析方法称为最坏性能分析（Worst-Case Analysis）,9,1.4 计算复杂性的概念,1.4.2 多项式时间算法,10,1.4 计算复杂性的概念,1.4.2 多项式时间算法,算法复杂性研究中:常将算法的计算时间表示为：问题中的简单而典型的参数(如网络优化中n,m),以及 问题中出现的数值(如弧上的权)的最大值(按绝对值)K等自变量的函数关系,如果算法运行时间的上界是m,n和K的多项式函数，则称相应的算法为伪多项式（Pseudopolynomial）（时间）算法，或拟多项式（时间）算法.,实际问题的输入规模/长度一定是m,n和logK的一个多项式函数.所以：多项式算法等价于其运行时间的上界是m,n和logK的多项式函数.,特别地,如果运行时间的上界是m,n的多项式函数（即该多项式函数不包含logK）,则称相应的算法为强多项式(Strongly Polynomial)时间算法.,一般来说，伪多项式算法并不是多项式算法.,11,1.4 计算复杂性的概念,TSP等许多问题至今没有找到多项式时间算法,但尚未证明其不存在,定义1.5 对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算法，则称给定的优化问题是多项式可解问题，或简称多项式问题，所有多项式问题集记为P(Polynomial).,同样道理,可以定义强多项式问题,伪多项式问题等.,TSP是否存在多项式时间算法?-这是21世纪数学和计算机科学的挑战性问题之一,1.4.3 多项式问题,12,网 络 优 化,第 1 章 概 论(第2讲),Network Optimization,清华大学数学科学系 谢金星办公室：理科楼2206#（电话：）http:/,1.5 NP,NPC和NP-hard概念(计算复杂性理论）,13,运筹学的ABC-A2B2C2（至少是组合优化、理论计算机科学的ABC）,Approximation Algorithm(近似算法)；Heuristic Branch and Bound（分枝定界）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),14,1.5.1 问题、实例与输入规模,评价一个算法的依据是该算法在最坏实例下的计算时间与实例输入规模的关系：,比多项式问题类可能更广泛的一个问题类是非确定多项式(Nondeterministic Polynomial，简记 NP)问题类,存在多项式算法的问题集合：多项式问题类（P）,存在多项式函数 g(x)满足上式时，算法为多项式算法,NP 类是通过判定问题引入的。,15,对任何一个优化问题，可以考虑其三种形式：最优化形式（原形：最优解）计值形式（最优值）判定形式（上界）,定义1.6 如果一个问题的每一个实例只有“是”或“否”两种答案，则称这个问题为判定问题(Decision/recognition/feasibility problem).称有肯定答案的实例为“是”实例(yes-instance).称答案为“否”的实例为“否”实例或非“是”实例(no-instance).,1.5.2 判定问题-定义,例1.13 线性规划问题(LP)的判定形式LP判定问题：给定一个实数值z，(LP)是否有可行解使其目标值不超过z？即：给定z，是否有?,难度降低,就有效算法的存在性而言，通常认为三种形式等价！,16,文字集,例1.15 适定性问题(Satisfiability problem)在逻辑运算中，布尔变量x的取值只有两个：“真”(1)和“假”(0)，逻辑运算有“或（+）”，“与（）”和“非（）.,1.5.2 判定问题-例,存在真值分配的表达式称为适定的(可满足的),文字集的任意一个子集中各元素（布尔变量）的“或”运算组成一个句子,多个句子的“与”运算组成一个表达式，如,适定性问题：给定布尔表达式，（SAT）是适定的吗？,17,1.5.2 判定问题-例,例1.16 三精确覆盖(3-Exact Covering：X3C)已知 的n个子集构成的子集族，其中每个子集包含S中三个元素，F中是否存在m个子集，使得？若m个子集满足上式，则称这m个子集精确覆盖S.,18,定义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一起构成一个算法，称为非确定多项式（时间）算法。,19,所以，可以从讨论基本可行解的性质入手,整系数问题等价于有理系数问题,1.5.3 非确定多项式问题类(NP)例,例1.17 整系数（或有理系数）的LP判定问题属于NP.,其实，LPP，所以LPNP.下面考虑通过定义来说明 LPNP,分析与思考：(注意：第1次印刷版教材上的证明可能有漏洞),（不）等式组有可行解，等价于它有基本可行解,LP判定问题等价于验证如下（不）等式组的可行解问题 因此可以不考虑目标函数问题，仍记为,20,1.5.3 非确定多项式问题类(NP)例,引理1.1 LP问题的约束的基本可行解的各分量值有界，其二进制字符串表达式的输入长度不超过,例1.17 整系数（或有理系数）的LP判定问题属于NP.（续）,输入长度不超过,又，分量值不超过,21,验证时最多需(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.,22,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.,23,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,多项式转换(定义),24,进一步，该映射可以在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）线性规划（判定）问题,25,进一步，该映射可以在 X3C 实例的输入长度的多项式时间内完成,特殊0-1背包判定问题（本书后面简称0-1背包判定问题）:对给定的整数 和b，是否存在1,2,.,n的子集B，使得?,例1.21 三精确覆盖多项式转换为0-1背包判定问题,1.5.3 非确定多项式问题类(NP)多项式转换,所以，三精确覆盖问题多项式转换为0-1背包判定问题,26,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).,多项式归约(定义),27,问题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的多项式归约,28,1.5.4 NP完全问题类(NPC)-多项式归约（例）,例1.22 适定问题多项式归约为三精确覆盖问题,（证明较繁，略）课后自己看书体会证明技巧,29,定义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.,30,1.5.4 NP完全问题类(NPC)证明,例1.23(Cook定理，1971）SATNPC.,前面已经证明SATNP，所以尚需证明：任何一个NP问题可以多项式归约为SAT,计算复杂性理论的奠基性工作之一：第一个被证明的NPC问题！是证明许多其他NPC问题的出发点,基本思想：若ANP，则A存在非多项式时间算法（猜测解、验证解）。对猜测解、验证解的过程进行分析，构造一个SAT问题！,（证明细节较繁，略）,31,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,32,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,33,1.5.4 NP完全问题类(NPC)证明（例）,例1.27（集合）划分（PARTITION）问题是NPC.,PARTITION问题：给定整数，是否存在1,2,.,n的一个子集S，使得？,要证明PARTITIONNPC，尚需证明：,这是（特殊）（0-1）背包判定问题的一个特殊情况，包的容积 背包判定问题NP PARTITIONNP,所有NP问题多项式转换/归约为集合划分问题，或：,某个NPC问题多项式转换/归约为集合划分问题,可以证明：背包问题多项式转换为集合划分问题,34,观察：,1.5.4 NP完全问题类(NPC)证明（例）,例1.27 PARTITION问题是NPC.（续）,这个映射满足“转换”定义的性质-转换的多项式性,证明：背包问题多项式转换为集合划分问题,给定0-1背包判定问题的任何一个实例构造集合划分问题的实例其中,这个映射满足“转换”定义的性质-解的一一对应性,35,1.5.4 NP完全问题类(NPC)证明（例）,例1.27 PARTITION问题是NPC.（续）,存在1,2,.,n的子集S，使得 的充分必要条件是存在1,2,.,n+2的一个子集S使得.,于是存在1,2,.,n的子集S，使得 即,36,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）,37,1.5.4 NP完全问题类(NPC)补充说明:,算法复杂性研究中:常将算法的计算时间表示为：问题中的简单而典型的参数(如网络优化中n,m),以及 问题中出现的数值(如弧上的权)的最大值(按绝对值)K，等自变量的函数关系,实际问题的输入规模/长度一定是m,n和logK的一个多项式函数.所以,如果一个算法是多项式时间算法,则运行时间的上界一定也是m,n和logK的多项式函数.,特别地,如果运行时间C(I)的上界是m,n的多项式函数（即该多项式函数不包含logK）,则称相应的算法为强多项式（Strongly Polynomial）时间算法，简称强多项式算法.,强多项式算法/问题,存在强多项式算法的问题称为强多项式问题.,38,1.5.4 NP完全问题类(NPC)补充说明,如果算法运行时间的上界是m,n和K的多项式函数，则称相应的算法为伪多项式（Pseudopolynomial）(时间)算法，或拟多项式(时间)算法。,如果采用“一进制”编码（Unary Encoding,即用x位表示一个正整数x），则伪多项式算法运行时间的上界是实例输入长度的多项式函数。,除非 P=NP,否则不存在伪多项式算法的NPC问题称为强NPC（Strongly NPC）问题，有时也称为Unary-NPC问题。,TSP、SAT等是强NPC问题,而背包问题则不是强NPC问题.,伪多项式算法、强NPC问题,由于采用“一进制”编码在当前的计算机上是不现实的，所以一般来说,伪多项式算法并不是多项式算法.,39,1.5.4 NP完全问题类(NPC)补充说明,例 TSP问题的余已知n，n阶整数矩阵dij，整数K，所有的环游长度都大于K吗？,但是，不能证明一个NP问题的余问题也是NP的！（这是因为对于NP问题的否实例，我们前面并没有关心其判定算法）,定义 对判定问题A和B，如果B的所有是实例（编码）正好都不是A的是实例（编码），则称B是A的余（Complement），记B=,定理 若A P，则 P,定义 所有NP问题的余记为Co-NP；所有NPC问题的余记为Co-NPC,Co-NP类,40,1.5.4 NP完全问题类(NPC)补充说明,定义 对一个问题，如果存在一个算法，其运算能被限制在以实例输入长度的多项式为界的空间内进行，则该问题称为多项式空间的。所有多项式空间的问题的集合称为PSPACE（多项式空间问题类）,定理 P PSPACE，NP PSPACE，Co-NP PSPACE,有些问题是不可计算的，如停机问题,定义 若A PSPACE，且所有PSPACE问题都可以多项式归结为A，则A称为PSPACE完备的（PSPACE-Complete）。,多项式空间问题,41,1.5.4 NP完全问题类(NPC)补充说明,想象的问题类示意图,P,NP,NPC,co-NP,co-NPC,PSPACE-COMPLETE,PSPACE,Stongly NPC,Stongly P,Pseudo-Polynomial,Stongly NPC的余,42,1.5.4 NP完全问题类(NPC)补充说明,上图中所有问题类可能最后都收缩为一个点-P,P=NP吗？-这是21世纪数学和计算机科学的挑战性问题之一,