NP完全性精讲课件.ppt

第五章 NP-完全性NP Completeness,第五章 NP-完全性,内容提要,多项式时间,多项式时间归约,多项式时间可验证算法,多项式时间可判定算法优化问题及其相关的判定问题P,NP,NP-难,NP-完全,CO-P,CO-NP电路可满足性问题是NP-完全问题若干NP-完全性问题的证明,内容提要 多项式时间,多项式时间归约,多项式时间可验证算法,重点与难点,重点:多项式时间归约P,NP,NP-难,NP-完全,CO-P,CO-NP电路可满足性问题是NP-完全问题难点:若干NP-完全性问题的证明,重点与难点 重点:,学习目的与要求,理解多项式时间,多项式时间归约,多项式时间可验证算法,多项式时间可判定算法,优化问题及其相关的判定问题,P,NP,NP-难,NP-完全,CO-P,CO-NP,电路可满足性问题是NP-完全问题.掌握若干NP-完全性问题的证明方法.,学习目的与要求 理解多项式时间,多项式时间归约,多项式时间可,NP-完全性简介,NP-完全性简介,NP-完全性,有的问题是难解的( intractable): 当问题规模变得越来越大时,我们不能在合理的时间内求得问题的解.什么才算是合理时间? 标准定义: 多项式时间(polynomial time)对于规模为 n的输入, 最坏情况时间复杂度为 O(nk) ,其中k是某一常数.多项式时间: O(n2), O(n3), O(1), O(n lg n) 非多项式时间: O(2n), O(nn), O(n!),NP-完全性有的问题是难解的( intractable):,多项式时间算法,多项式时间可解问题P表示多项式时间可解的问题类.所有问题都能在多项式时间内可解?图灵机“停机问题”是不可解问题。不管用多长时间、多大规模的计算机。波斯特(POST)对应问题是不可解问题。这些问题是难解问题, 且没有多项式时间算法,多项式时间算法多项式时间可解问题,POST 对应问题,POST 对应问题,波斯特对应问题实例：=0，1例1. A=1,10,011, B=101,00,11其解为：（1，3，2，3）1011 10 011例2. A=1，10111，10，B=111，10，0其解为(2,1,1,3)或(2,1,1,3,2,1,1,3)例3.A=10,011,101,B=101,11,011这个PCP问题实例无解。,波斯特对应问题实例：,NP-完全问题,NP-完全问题是这样一个其求解难度未知的问题类：至今还没有发现有多项式时间算法来求解也没有给出其求解时间以超多项式为下界我们把它叫做 P = NP 问题该问题是计算机科学领域中最大问题。也是一个21世纪的难题。NP 是Non-deterministic Polynomial 的缩写,NP-完全问题NP-完全问题是这样一个其求解难度未知的问题类,NP完全理论 概述问题Q的多项式时间算法：最坏情况时间复杂度f(n)=O(nk),k是某一常数。易解问题：有多项式时间算法；难解问题：需要超多项式时间。,NP完全理论,有些问题描述相似但其求解难度有本质不同：最短路径问题 V.S. 最长路径问题Eular回路问题 V.S. Hamilton回路问题2CNF可满足性问题 V.S. 3-CNF可满足性问题,有些问题描述相似但其求解难度有本质不同：,NP完全性精讲课件,NP-完全性及P类、NP类简介P类：多项式时间可解的问题类。NP类：多项式时间可验证的问题类。P,NP, NPC,NP.,注意：P类问题、NP类问题都是指判定问题,NP-完全性及P类、NP类简介NP, NPCNP. 注意：P,2CNF可满足问题是P问题。,2CNF可满足问题是P问题。,例如，,强连通分支:,例如，强连通分支:,结论2-CNF公式可满足当且仅当其关联有向图中任一强连通分支上不出现互为否定的文字。,结论,具有相同的可满足性。,具有相同的可满足性。,K-CNF:一个布尔公式称为k-CNF公式,如果它是一个CNF公式且它的每个子句恰有k个变元或变元的负出现。可满足公式:一个布尔公式称为可满足的,如果存在对该公式中的变量的一种赋值，使得布尔公式取值为真。,K-CNF:一个布尔公式称为k-CNF公式,如果它是一个CN,k-CNF可满足问题：任给定一个k-CNF公式F，问F是否可满足？2CNF可满足问题多项式时间可判定k-CNF可满足问题NP-完全（,）。,k-CNF可满足问题：任给定一个k-CNF公式F，问F是否可,判定问题与优化问题优化问题：有若干个可行解，每个可行解有一个值与它相关联，求有最优值的可行解。如最短路径问题SHORTEST-PATH.判定问题：只要求回答“是”或“不是(YES/NO),判定问题与优化问题,每个优化问题都有其关联的判定问题（判定问题与优化问题的关系）。对于一个给定的优化问题，通常对进行优化的值作限界后可得到关联的判定问题。,每个优化问题都有其关联的判定问题,SHORTEST-PATH要优化的值：路径长度给定图G，顶点u和v，限界：非负整数,N是自然数集。最短路径问题SHORTEST-PATH相关联的判定问题PATH：给定一个图G，顶点u和v及非负整数k,问是否有u到v的包含边数至多是k的路径？,SHORTEST-PATH要优化的值：路径长度N是自然数集。,优化问题与其相关联的判定问题的难易程度：如果一个优化问题是容易的，那么其相关联的判定问题也是容易的。反过来，如果优化问题的相关联的判定问题是难的，那么优化问题本身一定是难的是。SHORTEST-PATH是容易的，因此PATH是容易的。(为什么?),优化问题与其相关联的判定问题的难易程度：,归约设A，B是两个不同的判定问题。,是问题A的一个实例，,是问题B的一个实例。,归约是问题A的一个实例，是问题B的一个实例。,多项式时间归约算法：将问题A的任一实例,变换到问题B中的实例,且满足以下条件：,变换在多项式时间内完成；对,回答“YES”当且仅当对,回答“YES”。,2.如果存在问题A到问题B的多项式时间归约算法, 问题B有多项式时间判定算法，则问题A必有多项式时间判定算法。,多项式时间归约算法：将问题A的任一实例变换到问题B中的实例且,问题A的判定算法如下图所示：,YES,NO,YES,NO,问题A的判定算法如下图所示： YESNOYESNO,解释如下：给定问题A的一个实例 ,利用多项式时间归约算法将,变换成问题B的实例 ;,对问题B的实例,运行问题B的多项式时间判定算法；2.将对,的回答作为对,的回答。,解释如下：利用多项式时间归约算法将变换成问题B的实例,上面通过归约技术，利用问题B的易解来证明问题A的易解。利用归约技术，我们可以利用问题A是NP-完全问题来证明问题B是NP-完全问题。,上面通过归约技术，利用问题B的易解来证明问题A的易解。,“第一个”NP-完全问题本章使用的第一个NP-完全问题是“电路可满足问题”。给定一个由与门、或门、非门组成的布尔组合电路，问是否有电路的一组输入使电路输出1。,“第一个”NP-完全问题,34.1 多项式时间的定义,抽象问题Q是一个定义在问题实例集合I和问题解集合S上的一个二元关系。,如，SHORTESTPATH的问题实例是一个三元组(G,u,v)。问题的解就是图中的一个顶点序列（包括空序列，表示无路径存在）。,34.1 多项式时间的定义抽象问题Q是一个定义在问题实例集合,显然，SHORTESTPATH是一个关系。（由于最短路径未必唯一，因此一个给定问题实例可能有多个解。）,显然，SHORTESTPATH是一个关系。,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性与归约性,NP完全性与归约性,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,x1,x1,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性的证明,NP完全性的证明,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,若干NP完全问题,若干NP完全问题,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,NP完全性精讲课件,小结,本章主要讨论了多项式时间,多项式时间归约,多项式时间可验证算法,多项式时间可判定算法;优化问题及其相关的判定问题;P,NP,NP-难,NP-完全,CO-P,CO-NP;电路可满足性问题是NP-完全问题;若干NP-完全性问题的证明方法.,小结本章主要讨论了多项式时间,多项式时间归约,多项式时间可验,