文档介绍：第七章NP问题选讲邹权(博士)。NP问题是所有可用多项式时间算法验证其猜测准确性的判定问题的集合。PNPP=NP?P≠NP!-n-np/多项式时间规约问题A能够多项式时间规约到B说明:B比A难!NP完全问题,满足:P-(合取范式):如果一个布尔公式是一些子句的合取(与),而且子句是一个文字或多个文字的析取(或),F。F中每个子句都有且只有3个不同的文字,F。例:(x1¬x1¬x2)(x3x2x4)(¬x1¬x3¬x4),一个团即图G的一个完全子图最大团问题即是否可以找出一个团,使得其包含的顶点个数大于k顶点覆盖问题对于无向图G=(V,E),是否可以找出子集V’,使得如果边(u,v)∈E,则u∈V’或v∈V’,且|V’|<F可满足问题是一个NPC问题,试证明最大团问题也是NPC问题首先易证最大团是一个NP问题。Fφ构造一个图G。Fφ可满足当且仅当图G有一个大小为k的团。多项式规约说明:如果最大团问题可以多项式时间解决,F亦可以。也就是说:F容易!已知最大团问题是一个NPC问题,试证明顶点覆盖问题也是NPC问题首先易证顶点覆盖是一个NP问题。为最大团的图G构造一个图G’然后欲证图G有一个大小为k的团当且仅当图G’有一个大小为|V|-k的顶点覆盖多项式规约说明:顶点覆盖不会比最大团问题容易!如果最大团是NPC,顶点覆盖也是NPC。F-SATCliqueVertexCoverSubsetSumHamCycleTSPGraphColoringSetCoverPartitionBinPackingParallelSchedulingKnapsackStripPacking以往的转化欲解决问题A,将其转化为较简单的问题B,然后解决B,从而解决A本章的转化(多项式规约)欲证明B不可解,找一个不可解(NP完全)的问题A,将A多项式规约到B,从而说明B比A难,B也不可解对比