《算法设计技巧与分析》 第10章 NP完全问题 朱友文 zhuyw@nuaa.edu.cn
10.1 引言 判定问题与最优化问题 判定问题 最优化问题 2019/5/29 南京航空航天大学 计算机学院
10.2 P类问题 P类问题:对于判定问题Π,如果存在确定性算法A,且A可以在多项式时间内对问题Π进行判定或者求解。 2019/5/29 南京航空航天大学 计算机学院
10.3 NP类问题 NP类问题:对于判定问题Π,如果存在确定性算法A,且A可以在多项式时间内指出某个答案是否是问题Π的解。 2019/5/29 南京航空航天大学 计算机学院
10.4 NP完全问题 归约: TT T x T(x) 解 2019/5/29 南京航空航天大学 计算机学院
10.4 NP完全问题 NP完全问题 如果问题Π是NP问题 如果能够在多项式时间内求解问题Π ,那么就可以在多项式时间内求解任何一个NP问题 2019/5/29 南京航空航天大学 计算机学院
10.4 NP完全问题 NP完全问题 如果可以找到一个多项式时间的算法A求解某个NP完全问题Π,那么所有的NP问题就可以在多项式时间内求解,也就是说 NP=P 这是个机会? 2019/5/29 南京航空航天大学 计算机学院
10.4 NP完全问题 NP完全问题:举例 合取范式(CNF)可满足问题 哈密顿回路问题 顶点覆盖问题 2019/5/29 南京航空航天大学 计算机学院
10.4 NP完全问题 如何证明一个问题X是NP完全问题? 证明X是NP问题 证明存在一个已知的NP完全问题Y可以归约到X 2019/5/29 南京航空航天大学 计算机学院