计算复杂性的概念.ppt

《计算复杂性的概念.ppt》由会员分享，可在线阅读，更多相关《计算复杂性的概念.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.4 1.4 计算复杂性的概念计算复杂性的概念 定定义义1.3 1.3 所所谓谓组组合合(最最)优优化化(Combinatorial(Combinatorial Optimization)Optimization)又又称称离离散散优优化化（Discrete Discrete OptimizationOptimization），它它是是通通过过数数学学方方法法去去寻寻找找离离散散事事件件的的最最优优编排、分组、次序或筛选等编排、分组、次序或筛选等.这类问题可用数学模型描述为：这类问题可用数学模型描述为：优优 化化 问问 题题 三三 要要 素素:(Min,f,F)或或(Max,f,F)其其中中D

2、表表示示有有限限个个点点组组成成的的集集合合(定定义义域域),f为为目目标标函函数数,F=x|x D,g(x)0为可行域为可行域 1.4.1 1.4.1 组合优化组合优化 定义定义11.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.1 1.4.1 组合优化组合优化 例例例例1.7 0-11.7 0-1背包问题背包问题(knapsack problem)给给定定n个个容容积积分分别别为为ai，价价值值分分别别为为ci的的物物品品.设设有有一一个个容容积积为为b的的背背包包，如如何何以最大的价值装包？用数学规划模型表示为：以最大的价值装包？用数学规划模型表示为：D=0,1n例例1.10 1

3、.10 装箱问题装箱问题(Bin Packing)(Bin Packing)以以尺尺寸寸为为1 1的的箱箱子子装装进进给给定定的的n n个个尺尺寸寸不不超超过过1 1的的物物品品，如如何何使使所所用的用的箱子箱子个数最少个数最少?21.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.1 1.4.1 组合优化组合优化 例例例例1.9 1.9 整数线性规划整数线性规划(Integer Linear Programming)(Integer Linear Programming)(IP).我我们们假假设设线线性性整整数数规规划划的的参参数数（约约束束矩矩阵阵和和右右端端项项系系数数）都都是是整

4、整数数(或或有理数有理数).许许多多组组合合优优化化问问题题可可以以用用整整数数规规划划模模型型表表示示,但但有有时时不不如如直直接接用用自自然然语语言描述简洁言描述简洁 31.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.2 1.4.2 多项式时间算法多项式时间算法 对对于于组组合合优优化化问问题题，我我们们关关心心的的一一般般不不是是最最优优解解的的存存在在性性和和唯唯一一性性，而而是是如如何何找找到到有有效效的的算算法法求求得得一一个个最最优优解解.那那么么如如何何衡衡量量算算法法的的优优劣劣、有效与无效呢？有效与无效呢？完全枚举法可以求得最优解,但枚举时间有时不可能接受ATSP

5、:(ATSP:(n-1)!-1)!枚举(TOUR,周游或环游)设计算机每秒进行100亿次枚举,需30!/10e+10 2.65e+22(秒)即 2.65e+22/(365*24*60*60)8.4e+13(年)41.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.2 1.4.2 多项式时间算法多项式时间算法 构构造造算算法法的的目目的的是是能能够够解解决决问问题题（或或至至少少是是问问题题某某个个子类）的所有实例而不单单是某一个实例子类）的所有实例而不单单是某一个实例 问题（Problem）是需要回答的一般性提问，通常含有若干个满足一定条件的参数.问题通过下面的描述给定：（1）描述所有参

6、数参数的特性，（2）描述答案答案所满足的条件.问题中的参数赋予了具体值的例子称为实例(instance).衡衡量量一一个个算算法法的的好好坏坏通通常常是是用用算算法法中中的的加加、减减、乘乘、除除和和比比较较等等基基本本运运算算的的总总次次数数（计计算算时时间间）C（I）同同实实例例I在在计计算算机机计计算算时时的的二二进进制制输输入入数数据据(输输入入规规模模/长度长度d（I）)的大小关系来度量的大小关系来度量.计算模型计算模型C(I)=f(d(I):该函数关系称为算法的计算复杂性（度）计算复杂性（度）51.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.2 1.4.2 多项式时间算法

7、多项式时间算法 对于一个正整数对于一个正整数x，二进制表示是以，二进制表示是以如ATSP:二进制输入长度总量不超过(不考虑正负号、分隔符等)的系数来表示，其中，的系数来表示，其中，x的二进制数的位数不超过假设每一个数据(距离)的绝对值都有上界K 输入长度是输入长度是n的多项式函数的多项式函数所以网络优化中常用n,m等表示输入规模 61.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.2 1.4.2 多项式时间算法多项式时间算法 例例 构造构造算法算法将将n个自然数从小到大排列起来个自然数从小到大排列起来 算法 输入自然数自然数a(1),a(2),a(n).for(i=1;in;i+)fo

8、r(j=i+1;ja(j)k=a(i);a(i)=a(j);a(j)=k;即该算法的计算复杂性（度）为即该算法的计算复杂性（度）为O(n2 2)基本运算的总次数基本运算的总次数(最坏情形）：最坏情形）：2n(n-1)=O(n2 2)比较：比较：（n-1)+(n-2)+1=n(n-1)/2n-1)+(n-2)+1=n(n-1)/2赋值：赋值：3(n-1)+(n-2)+1=3n(n-1)/23(n-1)+(n-2)+1=3n(n-1)/271.4 1.4 计算复杂性的概念计算复杂性的概念 定定义义1.4 假假设设问问题题和和解解决决该该问问题题的的一一个个算算法法已已经经给给定定，若若存存在在g(

9、x)为为多多项项式式函数且对该问题函数且对该问题任意的一个实例任意的一个实例I，使得计算时间，使得计算时间成成立立，则则称称该该算算法法为为解解决决该该问问题题的的多多项项式式(时时间间)算算法法(Polynomial time algorithm).当当不不存存在在多多项项式式函函数数g(x)使使得得上上式式成成立立时时，称称相相应应的的算算法法是是非非多多项项式式时时间算法间算法,或指数或指数(时间时间)算法算法(Exponential time algorithm)输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢.1.4.2 1.4.2 多项式时间算法多项式时间算法注：上

10、面定义中，要求对该问题的任意一个实例均成立注：上面定义中，要求对该问题的任意一个实例均成立 ，这种分析方法称为这种分析方法称为最坏性能分析（最坏性能分析（Worst-Case AnalysisWorst-Case Analysis）81.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.2 1.4.2 多项式时间算法多项式时间算法 近似值计算机提速10倍n10100100010121013nlogn3366499660.9e110.87e12n21001041061063.16e6n310001061091042.15e4108n410121016102010182n10241.27e30

11、 1.05e301 404310n1010101001010001213nlogn20791.93e13 7.89e297995n!3628800101584e2567141591.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.2 1.4.2 多项式时间算法多项式时间算法 算法复杂性研究中算法复杂性研究中:常将算法的计算时间表示为：问题中的简单而典型的参数(如网络优化中网络优化中n,m),以及 问题中出现的数值(如弧上的权)的最大值(按绝对值)K等自变量的函数关系如如果果算算法法运运行行时时间间的的上上界界是是m,n和和K的的多多项项式式函函数数，则则称称相相应应的的算算法法为为伪伪多

12、项式（多项式（PseudopolynomialPseudopolynomial）（时间）算法，或拟多项式（时间）算法）（时间）算法，或拟多项式（时间）算法.实际问题的输入规模/长度一定是m,n和logK的一个多项式函数.所以：多项式算法等价于其运行时间的上界是m,n和logK的多项式函数.特别地,如果运行时间的上界是m,n的多项式函数（即该多项式函数不包含logK）,则称相应的算法为强多项式(Strongly Polynomial)时间算法.一般来说，伪多项式算法并不是多项式算法一般来说，伪多项式算法并不是多项式算法.101.4 1.4 计算复杂性的概念计算复杂性的概念 TSP等许多问题至今没

13、有找到多项式时间算法,但尚未证明其不存在定义定义1.5 对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算法，则称给定的优化问题是多项式可解问题，或简称多项式问题，所有多项式问题集记为P(Polynomial).同样道理,可以定义强多项式问题,伪多项式问题等.TSP是否存在是否存在多项式时间算法?-这是21世纪数学和计算机科学的挑战性问题之一1.4.3 多项式问题多项式问题11网网 络络 优优 化化 第第 1 1 章章 概概 论论 (第第2 2讲讲)Network Optimization清华大学数学科学系 谢金星办公室：理科楼2206#（电话：）http:/ 1.5 NP,NP

14、CNP,NPC和和NP-hardNP-hard概念概念(计算复杂性理论）计算复杂性理论）12运筹学的运筹学的ABC -ABC -A2B2 2C2 2 （至少是组合优化、理论计算机科学的（至少是组合优化、理论计算机科学的ABCABC）q Approximation Algorithm(Approximation Algorithm(近似算法近似算法)；HeuristicHeuristicq Branch and Bound Branch and Bound（分枝定界）分枝定界）q Computational Complexity Computational Complexity（计算复杂性）计算

15、复杂性）口莫开，开口常说错。口莫开，开口常说错。理论在监督，理论在监督，众目睽睽难逃脱。众目睽睽难逃脱。计算复杂性理论的计算复杂性理论的“Bible”“Bible”Garey Garey M M R.and R.and Johnson.D Johnson.D S,S,Computers Computers and and intractability intractability:a a guide guide to to the the theory theory of NP-completeness.San Francisco:.W.H.Freeman and Co.,1979 of NP

16、-completeness.San Francisco:.W.H.Freeman and Co.,1979 (中译本中译本:计算机和难解性：计算机和难解性：NP-CNP-C理论导论理论导论.张立昂等译张立昂等译,科学出版社，科学出版社，1987)1987)131.5.1 1.5.1 问题、实例与输入规模问题、实例与输入规模评评价价一一个个算算法法的的依依据据是是该该算算法法在在最最坏坏实实例例下下的的计计算算时时间间与与实例输入规模的关系：实例输入规模的关系：问题实例TSP问题中各参数:100个城市，城市间距离已知.背包问题问题中各参数:4个物品，大小分别为4,3,2,2.价值分别为8,7,5

17、,7.包的大小为6.整数线性规划问题中的n,A,b,c已知.比比多多项项式式问问题题类类可可能能更更广广泛泛的的一一个个问问题题类类是是非非确确定定多多项项式式(Nondeterministic Polynomial，简记，简记 NP)问题类问题类 存在多项式算法的问题集合：多项式问题类（存在多项式算法的问题集合：多项式问题类（P）存在多项式函数存在多项式函数 g(x)满足上式时，算法为多项式算法满足上式时，算法为多项式算法NP 类是通过类是通过判定问题判定问题引入的。引入的。14对任何一个优化问题，对任何一个优化问题，可以考虑其三种形式：可以考虑其三种形式：最优化形式（原形：最优解）最优化形

18、式（原形：最优解）计值形式（最优值）计值形式（最优值）判定形式（上界）判定形式（上界）定定义义1.6 1.6 如如果果一一个个问问题题的的每每一一个个实实例例只只有有“是是”或或“否否”两两种种 答答 案案，则则 称称 这这 个个 问问 题题 为为 判判 定定 问问 题题(Decision(Decision/recognition recognition/feasibility feasibility problem).problem).称称有有肯肯定定答答案案的的实实例例为为“是是”实实例例(yes-instance).(yes-instance).称称答答案案为为“否否”的的实实例例为为“

19、否否”实例或非实例或非“是是”实例实例(no-instance).(no-instance).1.5.2 1.5.2 判定问题判定问题-定义定义 例例1.13 1.13 线性规划问题线性规划问题(LP)(LP)的判定形式的判定形式LPLP判定问题：判定问题：给给定定一一个个实实数数值值z z，(LP)(LP)是是否否有有可可行行解解使使其其目目标标值值不不超超过过z z？即：给定即：给定z z，是否有，是否有?难度降低就有效算法的存在性而言，通常认为三种形式等价！就有效算法的存在性而言，通常认为三种形式等价！15文字集文字集 例例 1.15 1.15 适适 定定 性性 问问 题题(Satisf

20、iability(Satisfiability problem)problem)在在逻逻辑辑运运算算中中，布布尔尔变变量量x的的取取值值只只有有两两个个：“真真”(1)”(1)和和“假假”(0)”(0)，逻逻 辑辑 运运 算算 有有“或或（+）”，“与（与（）”和和“非（非（）.1.5.2 1.5.2 判定问题判定问题-例例存在存在真值分配真值分配的表达式称为适定的的表达式称为适定的(可满足的可满足的)+0000111011110000101001110110文字集的任意一个子集中各元素（布尔变量）文字集的任意一个子集中各元素（布尔变量）的的“或或”运算组成一个运算组成一个句子句子,多个句子的

21、多个句子的“与与”运算组成一个运算组成一个表达式表达式，如，如 适定性问题：适定性问题：给定布尔表达式给定布尔表达式 ，（SATSAT）是适定的吗？是适定的吗？161.5.2 1.5.2 判定问题判定问题-例例例例1.16 三精确覆盖三精确覆盖(3-Exact Covering：X3C)已知已知 的的n个子集构成的子集族个子集构成的子集族 ，其中每个子集包含其中每个子集包含S中三个元素，中三个元素，F中是否存在中是否存在m个子集个子集 ，使得使得？若若m个子集满足上式，则称这个子集满足上式，则称这m个子集个子集精确精确覆盖覆盖S.17定义定义1.7 若存在一个多项式函数若存在一个多项式函数g(

22、x)和一个验证算法和一个验证算法H，对一类，对一类判定问题判定问题A的任何一个的任何一个“是是”实例实例I，都，都存在一个存在一个字符串字符串S是是I的可行解，满足其输入长度的可行解，满足其输入长度d(S)不超过不超过g(d(I)，其中，其中d(I)为为I的的输入长度，且算法输入长度，且算法H验证验证S为实例为实例I的可行解的计算时间的可行解的计算时间f(H)不不超过超过g(d(I)，则称判定问题，则称判定问题A是非确定多项式的。是非确定多项式的。考虑将求解判定问题的算法分为两个阶段：考虑将求解判定问题的算法分为两个阶段：（1 1）猜测阶段：求出或猜测该问题的一个解）猜测阶段：求出或猜测该问题

23、的一个解（2 2）检查或验证阶段：一旦解已经选定，将猜测的解作为输）检查或验证阶段：一旦解已经选定，将猜测的解作为输入，验证此解是否为该实例入，验证此解是否为该实例“是是”的回答的回答.我们称实例我们称实例“是是”回答的解为实例的回答的解为实例的可行解可行解，否则称为，否则称为不可行解不可行解.所有非确定多项式问题的集合用所有非确定多项式问题的集合用NP表示表示.1.5.3 1.5.3 非确定多项式问题类非确定多项式问题类(NP)(NP)定义构造字符串（解）的过程及验证算法构造字符串（解）的过程及验证算法H一起构成一个算法，称一起构成一个算法，称为为非确定多项式（时间）算法。非确定多项式（时间

24、）算法。18所以，可以从讨论基本可行解基本可行解的性质入手的性质入手 整系数问题等价于整系数问题等价于有理系数有理系数问题问题 1.5.3 1.5.3 非确定多项式问题类非确定多项式问题类(NP)(NP)例例例1.17 1.17 整系数（或整系数（或有理系数有理系数）的的LPLP判定判定问题问题属于属于NP.NP.其实，其实，LP LP P P，所以，所以LPLP NP.NP.下面考虑通过定义来说明LPLP NPNP分析与思考：(注意：第1次印刷版教材上的证明可能有漏洞)（不）等式组有可行解，等价于它有基本可行解（不）等式组有可行解，等价于它有基本可行解 LP判定问题等价于验证如下（不）等式组

25、的可行解问题判定问题等价于验证如下（不）等式组的可行解问题 因此可以不考虑目标函数问题，仍记为因此可以不考虑目标函数问题，仍记为19 1.5.3 1.5.3 非确定多项式问题类非确定多项式问题类(NP)(NP)例引理引理1.11.1 LP LP问题的约束的基本可行解的各分量值有界，其二进问题的约束的基本可行解的各分量值有界，其二进制字符串表达式的输入长度不超过制字符串表达式的输入长度不超过例例1.17 1.17 整系数（或整系数（或有理系数有理系数）的的LPLP判定判定问题问题属于属于NP.NP.（续）（续）输入长度不超过输入长度不超过又又 ，分量值不超过，分量值不超过20验证时最多需验证时最

26、多需(m+1)n个乘，个乘，(m+1)(n-1)个加或减，个加或减，n+m+1个比个比较较，共计共计LPLP实例的输入长度实例的输入长度d(I)满足满足 1.5.3 1.5.3 非确定多项式问题类非确定多项式问题类(NP)(NP)例LPLP的一个基本可行解的输入长度不超过的一个基本可行解的输入长度不超过例例1.17 1.17 整系数（或整系数（或有理系数有理系数）的的LPLP判定判定问题问题属于属于NP.NP.（续）（续）对对LP判判定定问问题题的的一一个个“是是”实实例例，上上述述约约束束组组（等等式式和和不不等等式式组组）一一定定存存在在一一个个基基本本可可行行解解.当当给给定定一一个个基

27、基本本可可行行解解x，只只要要验证是否满足验证是否满足？取多项式函数取多项式函数g(x)=2=2x2 2，则满足定义，所以，则满足定义，所以LPLP NP.NP.21F中中m个元素个元素 是是S的一个精确三覆盖的充分必要条件为：的一个精确三覆盖的充分必要条件为：相应的相应的m个向量满足个向量满足集集合合S中中共共有有3m个个元元素素，子子集集族族F中中的的每每个个子子集集合合对对应应一一个个3m维维向向量量：向向量量的的3m个分量对应个分量对应3m个元素，元素包含在对应子集中的分量为个元素，元素包含在对应子集中的分量为1，余下的为，余下的为0.例如：例如：S=，F中的一个元素中的一个元素 ，对

28、应向量为，对应向量为 =(1,1,0,0,0,1)，表示为一个字符串，表示为一个字符串(110001).1.5.3 1.5.3 非确定多项式问题类非确定多项式问题类(NP)(NP)例按字符串向量问题，精确三覆盖按字符串向量问题，精确三覆盖“是是”实例的任何一个解可以用长度为实例的任何一个解可以用长度为3m2 的字符表示的字符表示.验证是否可行解的算法最多需验证是否可行解的算法最多需3m2 个加法和个加法和3m个比较，算法的计算时间为个比较，算法的计算时间为3m2+3m.例例1.19 三精确覆盖属于三精确覆盖属于NP三精确覆盖问题任何一个实例的输入长度三精确覆盖问题任何一个实例的输入长度d(I)

29、3m.选选g(x)=x2/3+x，则定义条件满足，所以三精确覆盖属于，则定义条件满足，所以三精确覆盖属于NP.221.5.3 1.5.3 非确定多项式问题类非确定多项式问题类(NP)(NP)问题问题A2A2的难度不低于问题的难度不低于问题A1A1定义定义1.8 1.8 给定问题给定问题A1A1和和A2A2，若存在一个多项式算法，若存在一个多项式算法满足：满足：对对A1A1的的任任何何一一个个实实例例I1，算算法法将将实实例例I1的的输输入入转转换换为为A2A2的的一一个实例个实例I I2 2的输入；的输入；这这种种转转换换过过程程使使得得实实例例I1和和I I2 2的的解解一一一一对对应应，即

30、即将将实实例例I1的的一一个个解解x1的的输输入入转转换换为为实实例例I I2 2的的一一个个解解x2的的输输入入，且且x1为为I1的的“是是”答案答案 x2是是I I2 2的一个的一个“是是”答案；答案；则称则称A1A1问题多项式转换为问题多项式转换为A2A2问题问题，算法算法称为问题称为问题A1A1到问题到问题A2A2的一个多项式转换（算法）的一个多项式转换（算法）(Transformation).(Transformation).常用的研究方法常用的研究方法-多项式转换多项式转换(变换变换)、多项式归约、多项式归约(归结归结)若若A1A1多项式转换为多项式转换为A2A2，且A2PA2P，

31、则，则A1PA1P若若A1A1多项式转换为多项式转换为A2A2，且，且A2NPA2NP，则，则A1NPA1NP多项式转换(定义)23进一步，该映射可以在进一步，该映射可以在SAT实例的输入长度实例的输入长度 m n 的多项式时间内完成的多项式时间内完成SAT的一个实例是由的一个实例是由 n 个逻辑变量和个逻辑变量和 m 个句子组成，输入长度是个句子组成，输入长度是 m n.1.5.3 1.5.3 非确定多项式问题类非确定多项式问题类(NP)(NP)多项式转换 等价于一个整数（等价于一个整数（0-1）线性规划问题（目标可以任意）。）线性规划问题（目标可以任意）。例例1.20 1.20 适定性问题

32、多项式转换为整数（适定性问题多项式转换为整数（0-1）线性规划问题）线性规划问题.将将“真真”对应对应“1 1”，“假假”对应对应“0 0”，令逻辑变量，令逻辑变量 x 对应整数对应整数0或或1，对应对应1-x.含含n个变量的句子个变量的句子 (j=1,2,.,m)为为“真真”，对应下列不等式组，对应下列不等式组有可行解：有可行解：适定性问题多项式转换为整数（适定性问题多项式转换为整数（0-1）线性规划（判定）问题）线性规划（判定）问题24进一步，该映射可以在进一步，该映射可以在 X3C 实例的输入长度的多项式时间内完成实例的输入长度的多项式时间内完成特殊特殊0-1背包判定问题（本书后面简称背

33、包判定问题（本书后面简称0-1背包判定问题）背包判定问题）:对给定的整数对给定的整数 和和b，是是否否存存在在1,2,.,n的的子子集集B，使使得得?例例1.21 1.21 三精确覆盖多项式转换为三精确覆盖多项式转换为0-10-1背包判定问题背包判定问题1.5.3 1.5.3 非确定多项式问题类非确定多项式问题类(NP)(NP)多项式转换 所以，三精确覆盖问题多项式转换为所以，三精确覆盖问题多项式转换为0-10-1背包判定问题背包判定问题三精确覆盖实例的一个解一一对应背包问题实例的一个解：三精确覆盖实例的一个解一一对应背包问题实例的一个解：假设存在B1,2,.,n，使得 .由|B|不超过n，知

34、左边和式中（n+1)同次幂项的系数和不超过n（无进位）；又由b的每个幂次项系数为1,知左边和式中n+1的每个次幂项系数恰好为1.|jB 得S 的一个三精确覆盖251.5.4 NP1.5.4 NP完全问题类完全问题类(NPC)-(NPC)-定义定义1.9 1.9 已知判定问题已知判定问题A1A1和和A2A2，若存在多项式函数，若存在多项式函数 和和 ，使得对，使得对A1A1的任何实例的任何实例I I，在多项式时间内构造，在多项式时间内构造A2A2的一个实例，的一个实例，其输入长度不超过其输入长度不超过 ，并对，并对A2A2的任何一个算法的任何一个算法H2H2，都存在问题都存在问题A1A1的一个算

35、法的一个算法H1H1，使得，使得H1H1算法调用算法调用H2H2算法且使得算法且使得计算时间计算时间，其中其中fH1H1(x)和和fH2H2(x)分别表示算法分别表示算法H1H1和和H2H2的计算时间与实例输的计算时间与实例输入长度入长度x之间的关系，则称问题之间的关系，则称问题A1A1多项式归约为问题多项式归约为问题A2.A2.根据A2A2的算法的算法H2H2，构造构造A1A1的算法的算法H1H1的过程，即映射的过程，即映射 ：H2 H1H2 H1称为从称为从A1A1到到A2A2的一个多项式归约的一个多项式归约(reduction).(reduction).多项式归约多项式归约(定义定义)2

36、6问题问题A2A2的难度不低于问题的难度不低于问题A1 A1(注：第1次印刷版有误)若若A1A1多项式归约为多项式归约为A2A2，且A2PA2P，则，则A1PA1P若若A1A1多项式归约为多项式归约为A2A2，且，且A2NPA2NP，则，则A1NPA1NP若若A1A1多项式归约为多项式归约为A2A2，则当把，则当把H1H1对对H2H2的一次调用当成一次基本的一次调用当成一次基本运算时，运算时，H1 H1是是A1A1的多项式算法。的多项式算法。1.5.4 NP1.5.4 NP完全问题类完全问题类(NPC)-(NPC)-多项式归约多项式归约多项式转换是多项式归约多项式转换是多项式归约的特例的特例归

37、约映射可以如下构造：归约映射可以如下构造：H1 H1：STEP1 STEP1 用多项式转换将用多项式转换将A1A1的实例转换为的实例转换为A2A2的实例的实例 STEP2 STEP2 用用H2H2算法求解算法求解A2A2的实例的实例即多项式转换可以认为是只允许调用一次即多项式转换可以认为是只允许调用一次H2H2的多项式归约的多项式归约271.5.4 NP1.5.4 NP完全问题类完全问题类(NPC)(NPC)-多多项项式式归约归约 （例）（例）例例1.22 1.22 适定适定问题问题多多项项式式归约为归约为三精确覆盖三精确覆盖问题问题 （证明较繁，略）课后自己看书体会证明技巧28定定义义1.1

38、0 1.10（1 1）对对于判定于判定问题问题A A，若，若A A NPNP且且NPNP中的任何一个中的任何一个问问题题可在多可在多项项式式时间时间内内归约为归约为A A，则则称称A A为为NPNP完全完全问题问题(NP-(NP-CompleteComplete或或NPC).NPC).可以表示可以表示为为A A NPCNPC.NPC和NP-hard两者的区别是:验证一个问题A是否为NP-hard无须判断A是否属于NP.根据定义可知NPCNPH.当已知一个问题属于NPC或NPH时，如果再遇到一个新问题：（1）若已知问题多项式归约为新问题，则新问题属于NPH;1.5.4 NP1.5.4 NP完全问

39、题类完全问题类(NPC)(NPC)定定义义（2 2）对对于判定于判定问题问题A A，若，若NPNP中的任何一个中的任何一个问题问题可在多可在多项项式式时间时间归约为归约为判定判定问题问题A A，则则称称A A为为NPNP困困难问题难问题(NP-hard(NP-hard 或或NPH).NPH).可可以表示以表示为为A A NPH.NPH.（2）若还可以验证新问题属于NP，则新问题属于NPC.291.5.4 NP1.5.4 NP完全问题类完全问题类(NPC)(NPC)证明证明例例1.231.23(CookCook定理，定理，19711971）SATSAT NPC.前面已经证明SATSAT NP，所

40、以尚需证明：任何一个任何一个NPNP问题可以多项式归约为问题可以多项式归约为SATSAT计算复杂性理论的奠基性工作之一：第一个被证明的计算复杂性理论的奠基性工作之一：第一个被证明的NPCNPC问题！问题！是证明许多其他是证明许多其他NPCNPC问题的出发点问题的出发点基本思想：若A NP，则A存在非多项式时间算法（猜测解、验证解）。对猜测解、验证解的过程进行分析，构造一个SAT问题！（证明细节较繁，略）301.5.4 NP1.5.4 NP完全问题类完全问题类(NPC)(NPC)证明（例）证明（例）例例1.24 1.24 整数整数线线性性规规划划（ILPILP）的判定的判定问题问题属于属于NPC

41、NPC 例1.20已证明适定问题多项式转换为0-1线性规划(ZOLP)的判定问题 ZOLP判定问题属于NPH与线性规划的判定问题属于NP的证明类似，可以证明：整数线性规划的判定问题属于NP引理引理如果如果ILPILP有可行解，则它有一个可行解有可行解，则它有一个可行解推论：推论：ZOLPZOLP多项式等价多项式等价于于ILPILP；ILPILP的判定的判定问题问题属于属于NPCNPC易知：ZOLP的判定问题属于NP ZOLP判定问题属于NPC311.5.4 NP1.5.4 NP完全问题类完全问题类(NPC)(NPC)证明（例）证明（例）例例1.25 1.25 三精确覆盖三精确覆盖（X3CX3C

42、）属于属于NPC.NPC.SATSAT多多项项式式归约为归约为X3C X3C(例例1.221.22)X3CX3CNP NP（例例1.191.19）X3CX3C NPC NPC例例1.26 1.26（特殊）（特殊）（0-10-1）背包判定问题属于）背包判定问题属于NPC.NPC.X3CX3C多多项项式式变换变换为为背包判定问题背包判定问题（例例1.211.21）背包判定问题背包判定问题NP NP（易证易证）背包判定问背包判定问题题 NPC NPC321.5.4 NP1.5.4 NP完全问题类完全问题类(NPC)(NPC)证明（例）证明（例）例例1.27 1.27（集合）划分（集合）划分（PART

43、ITIONPARTITION）问题是）问题是NPC.NPC.PARTITION问题：给定整数 ，是否存在1,2,.,n的一个子集S，使得？要证明要证明PARTITIONNPCPARTITIONNPC，尚需证明：这是（特殊）（这是（特殊）（0-10-1）背包判定问题的一个特殊情况，包的容）背包判定问题的一个特殊情况，包的容积积 背包判定问题背包判定问题NP PARTITIONNPNP PARTITIONNP 所有NP问题多项式转换/归约为集合划分问题，或：某个NPC问题多项式转换/归约为集合划分问题 可以证明：背包问题多项式转换为集合划分问题 33观察：1.5.4 NP1.5.4 NP完全问题类

44、完全问题类(NPC)(NPC)证明（例）证明（例）例例1.27 PARTITION1.27 PARTITION问题是问题是NPC.NPC.（续）（续）这个映射满足这个映射满足“转换转换”定义的性质定义的性质-转换的多项式性转换的多项式性 证明：背包问题多项式转换为集合划分问题 给定给定0-10-1背包判定问题的任何一个实例背包判定问题的任何一个实例构造集合划分问题的实例其中这个映射满足这个映射满足“转换转换”定义的性质定义的性质-解的一一对应解的一一对应性性 341.5.4 NP1.5.4 NP完全问题类完全问题类(NPC)(NPC)证明（例）证明（例）例例1.27 PARTITION1.27

45、 PARTITION问题是问题是NPC.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，使得 即351.5.4 NP1.5.4 NP完全问题类完全问题类(NPC)(NPC)证明（例）证明（例）易证：装箱判定问题属于易证：装箱判定问题属于NPNP易证易证.例例1.28 1.28 装箱装箱(BP)(BP)判定问

46、题是判定问题是NPC.NPC.(注：第1次印刷版有漏洞)给定正整数K及n个物品，尺寸为(正整数)，是否能在K个尺寸为B(正整数)的箱子中装入这n个物品？要证明要证明BPNPCBPNPC，可将划分问题多项式转换为BP给定正整数 ,构造BP问题:K=2，这一过程可以在多项式时间内完成存在1,2,.,n的子集S，使得 的充分必要条件是在K=2个尺寸为B的箱子中可以装入这n个物品所以所以BPNPC BPNPC （思考：（思考：正整数集合划分问题NPCNPC）361.5.4 NP1.5.4 NP完全问题类完全问题类(NPC)(NPC)补充说明补充说明:算法复杂性研究中算法复杂性研究中:常将算法的计算时间

47、表示为：问题中的简单而典型的参数(如网络优化中网络优化中n,m),以及 问题中出现的数值(如弧上的权)的最大值(按绝对值)K，等自变量的函数关系实际问题的输入规模/长度一定是m,n和logK的一个多项式函数.所以,如果一个算法是多项式时间算法,则运行时间的上界一定也是m,n和logK的多项式函数.特别地,如果运行时间C(I)的上界是m,n的多项式函数（即该多项 式 函 数 不 包 含 logK）,则 称 相 应 的 算 法 为 强 多 项 式（Strongly Polynomial）时间算法，简称强多项式算法.强多项式算法强多项式算法/问题问题存在强多项式算法的问题称为强多项式问题.371.5

48、.4 NP1.5.4 NP完全问题类完全问题类(NPC)(NPC)补充说明补充说明如如果果算算法法运运行行时时间间的的上上界界是是m,n和和K的的多多项项式式函函数数，则则称称相相应应的的算算法法为为伪伪多多项项式式（PseudopolynomialPseudopolynomial）(时时间间)算算法法，或或拟拟多项式多项式(时间时间)算法。算法。如如果果采采用用“一一进进制制”编编码码（Unary Unary Encoding,Encoding,即即用用x位位表表示示一一个个正正整整数数x），则则伪伪多多项项式式算算法法运运行行时时间间的的上上界界是是实实例例输输入入长长度度的多项式函数。的

49、多项式函数。除非除非 P=NP,否则不存在伪多项式算法的否则不存在伪多项式算法的NPC问题称为问题称为强强NPC（StronglyNPC）问题，有时也称为问题，有时也称为Unary-NPC问题。问题。TSP、SAT等是强NPC问题,而背包问题则不是强NPC问题.伪多项式算法、强伪多项式算法、强NPCNPC问题问题由由于于采采用用“一一进进制制”编编码码在在当当前前的的计计算算机机上上是是不不现现实实的的，所所以一般来说以一般来说,伪多项式算法并不是多项式算法伪多项式算法并不是多项式算法.381.5.4 NP1.5.4 NP完全问题类完全问题类(NPC)(NPC)补充说明补充说明例 TSP问题的

50、余已知n，n阶整数矩阵dij，整数K，所有的环游长度都大于K吗？但是，不能证明一个但是，不能证明一个NPNP问题的余问题也是问题的余问题也是NPNP的！的！（这是因为对于（这是因为对于NPNP问题的否实例，我们前面并没有关心其判定算法）问题的否实例，我们前面并没有关心其判定算法）定义 对判定问题A和B，如果B的所有是实例（编码）正好都不是A的是实例（编码），则称B是A的余（Complement），记B=定理 若A PP，则 PP定义 所有NP问题的余记为Co-NP；所有NPC问题的余记为Co-NPCCo-NPCo-NP类类391.5.4 NP1.5.4 NP完全问题类完全问题类(NPC)(NP