第九讲 NP完全问题 算法的设计与分析课件.pptVIP

* * * * * * * * * * * * * * 可满足性∝poly团集问题 对于任意一个合取范式，按照如下方式构造相应的图G： 例如 图G的每个顶点对应于f中的每个文字，多次出现的重复表示； 若图G中两个顶点对应的文字不互补，且不出现在同一子句中，则将其连线。（a-b连线意味着a和b同时为真） Algorithms Design Techniques and Analysis 设f有n个子句，则：f可满足 ? n个子句同时为真 ?每个子句至少1个文字为真 ?G中有n个顶点之间彼此相连 ?G中有n个顶点的团 显然，上述构造图G的方法可在多项式时间内完成，故有：SAT∝poly团问题。 由以上证明可知，团问题是NP完全问题。 SAT问题∝poly团问题 同时为真，则相连 Algorithms Design Techniques and Analysis Algorithms Design Techniques and Analysis 可满足性?poly顶点覆盖 给出一个可满足性实例I，我们把它变换为顶点覆盖的一个实例 I’，设I是一个有m个子句和n个布尔变元x1,x2,..,xn的可满足性实例公式f=C1?C2 ?… ?Cm ，构造I’如下。 对于f中的每一个布尔变元xi，G包含一对顶点xi和~xi ，它们有一条边相连; 对于每个子句Cj包含的nj个文字，G包含一个大小为nj的团集Cj ； 对于在Cj中的每个顶点w，有一条边连接w到(1)中构造的顶点对(xi,~xi)中它相应的文字。这些边称为连通边; 令 Algorithms Design Techniques and Analysis 引理 10.2 f是可满足的当且仅当构造的图有一个大小为k的顶点覆盖。 证明: P181 Algorithms Design Techniques and Analysis 引理 10.3 设G=(V,E)是连通无向图，那么S ? V是一个独立集当且仅当V-S是G的一个顶点覆盖。 证明 设e=(u,v)是G中的任意边，S是一个独立集当且仅当u或v至少有一个在V-S中，即V-S是G中的顶点覆盖。 顶点覆盖?poly独立集 Algorithms Design Techniques and Analysis 定理 10.4 顶点覆盖、独立集和团集问题是NP完全的。 Algorithms Design Techniques and Analysis 更多NP完全问题 P182 co-NP类由它们的补属于NP类的那些问题组成。例如： 旅行商问题的补：给出n个城市和它们之间的距离，不存在长度为k或更少的任何旅程，情况是那样吗? 可满足性问题(SAT)的补：给出一个公式f，不存在使得f为真的布尔变量指派，是吗? 换言之，f是不可满足的吗? 换个角度来看， co-NP类问题也是NP完全问题。 10.5 co-NP类 Algorithms Design Techniques and Analysis Algorithms Design Techniques and Analysis 10.5 co-NP类 co-NP类由它们的补属于NP类的那些问题组成。 定义 10.7 问题?对于co-NP类是完全的，如果 (1) ? 在 co-NP中 (2)对于co-NP中的每一个问题?’ ，?’ ?poly ? co-NP类问题 co-NP完全问题 Algorithms Design Techniques and Analysis co-NP类 定理10.5 问题∏是NP完全的，当且仅当它的补 对于类co-NP是完全的。 定理 10.6 重言式问题:给出一个DNF公式f，它是重言式吗? 这个问题对于co-NP类是完全的 由此得出下列结论: 重言式问题属于P当且仅当co-NP=P, 重言式问题属于NP当且仅当co-NP=NP 。 Algorithms Design Techniques and Analysis 10.6 NPI类 定理 10.7 如果问题∏和它的补 是NP完全的，那么co-NP=NP。 换句话说，如果问题∏和它的补都是NP完全的，那么NP类在补运算下是封闭的。 NPI class: the class of problems that they and their complementation are in NP, but are not NP-complete. 10.6 NPI类 NP类问题中还有一些问题，人们不知道是属于P类还是属于NP完全问题，还有待于证明其归属。 这些问题是NP完全问题的可能性非常小，也因为不相信他们在P中，我们人为地增加另一问题类来接纳这类问题，这个类称为