《高级算法设计》课件 第3章 NP问题.pptx

高级算法设计与分析NP问题林海lin.hai@whu.edu.cnB站：foretmer

主要内容基本概念、归约P问题的证明NPC问题的证明

算法效率多项式时间算法O(nc)forsomeconstantc非多项式时间算法复杂度为O(n)的算法是高效率?复杂度为O(nlogn)?O(n2)?O(n10)?O(nlogn)?O(2n)?O(n!)?

基本概念：P问题

基本概念：NP问题

基本概念：NPC问题

基本概念：关系P问题，NP问题和NP完全问题的关系（认为，没有得到证实）

基本概念：NPC问题判断是否NP问题也就是给出一个证书，可否在多项式时间内判断它是否是原问题的一个解最优化问题需要转化为判断性问题

基本概念：NPC问题旅行商问题转化为：此图中是否存在总权重为1的回路?此图中是否存在总权重为2的回路?…此图中是否存在总权重为n的回路?一个优化问题可分解为多个判定性问题如果能够证明一个判定性问题为NP难时，显然原问题也是NP难的

基本概念：归约性通俗的讲，一个问题(如Q1)可以规约为另外一个问题(如Q2)是指问题Q1可以转换为问题Q2，之后可以通过求解Q2的方法来求解Q1如:求解一元一次方程(问题Q1)可归为求解一元二次方程(问题Q2):一元二次方程的二次项系数为0即可，之后可以通过求解一元二次方程的方法来求解一元一次方程

基本概念：归约

基本概念：归约归约具有传递性如果问题A可归约为问题B，问题B可归约为问题C，则问题A一定可归约为问题C。

基本概念：归约证明

基本概念：归约性

主要内容基本概念、归约P问题的证明NPC问题的证明

P问题的证明2合取范式(CNF)的可满足性问题(SAT)

P问题的证明2合取范式(CNF)到图的转换

P问题的证明2合取范式(CNF)到图的转换

P问题的证明2合取范式(CNF)到图的转换当且仅当2CNF中存在子句(x∨y)，图G中存在边?x→y(和边?y→x)

P问题的证明

P问题的证明

P问题的证明

P问题的证明

P问题的证明

主要内容基本概念、归约P问题的证明NPC问题的证明

NPC问题的证明

第一个NPC问题电路可满足性问题问题：给定一个逻辑电路，问是否存在一种输入使输出为True其它的NPC问题都是由这个问题归约而来的。因此，逻辑电路问题是NPC类问题的“鼻祖”。有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题归约到它就行了

公式可满足性问题公式可满足性问题:

公式可满足性问题公式可满足性证明这是一个NP问题

公式可满足性问题公式可满足性证明归约证明：电路可满足性归约到公式可满足性显而易见，每个电路都可写成一个布尔公式也就是存在f，使得任何一个实例x属于电路，当且仅当f(x)属于公式但，直接写的话，因每个电路门输出线扇出为2或者2以上导致布尔公式的规模出现指数增长

公式可满足性问题公式可满足性证明我们的目的不是将电路转换为布尔公式，而是证明可满足性，如果电路有可满足指派，则电路每个门输出都由其输入决定，写成表达式如右x7

公式可满足性问题公式可满足性证明以上转换为多项式时间如果电路有可满足性实例，则电路输出为1，而公式输出也为1如果公式输出为1，则显然电路输出也为1公式可满足性为NPC问题

3-CNF可满足性问题每个子句有3个文字

3-CNF可满足性问题公式可满足性证明这是一个NP问题公式可满足性可以归约到3-CNF将布尔公式转换为子句的合取式将子句转换为合取范式将子句转为3个文字的合取取式

3-CNF可满足性问题1.将布尔公式转换为子句的合取式建立布尔公式的语法树

3-CNF可满足性问题1.将布尔公式转换为子句的合取式建立布尔公式的语法树将语法分析树看成电路，得出归约的布尔公式此布尔公式为合取式

3-CNF可满足性问题2.将子句转换为合取范式构造每个子句的真值表

3-CNF可满足性问题2.将子句转换为合取范式构造每个子句的真值表根据真值表中值为0的项，得出析取范式此析取范式等价于子句的否

3-CNF可满足性问题2.将子句转换为合取范式构造每个子句的真值表根据真值表中值为0的项，得出析取范式此析取范式等价于子句的否运用德摩根定律，得出合取子句（将析取范式再取否）

3-CNF可满足性问题3.将子句转为3个文字的合取取式

3-CNF可满足性问题以上映射为多项式时间将布尔公式转换为子句的合取式同布尔电路转换为布尔公式将子句转换为合取范式每个子句至多变为8个子句（至多3个变量）将子句转为3个文字的合取取式至多引入4个子句由以上步骤可知：3-CNF是可满足的当且仅当以上三个步骤的每一步都是可