Presentation is loading. Please wait.

Presentation is loading. Please wait.

《算法设计技巧与分析》 第10章 NP完全问题 朱友文 zhuyw@nuaa.edu.cn.

Similar presentations


Presentation on theme: "《算法设计技巧与分析》 第10章 NP完全问题 朱友文 zhuyw@nuaa.edu.cn."— Presentation transcript:

1 《算法设计技巧与分析》 第10章 NP完全问题 朱友文

2 10.1 引言 判定问题与最优化问题 判定问题 最优化问题 2019/5/29 南京航空航天大学 计算机学院

3 10.2 P类问题 P类问题:对于判定问题Π,如果存在确定性算法A,且A可以在多项式时间内对问题Π进行判定或者求解。 2019/5/29
南京航空航天大学 计算机学院

4 10.3 NP类问题 NP类问题:对于判定问题Π,如果存在确定性算法A,且A可以在多项式时间内指出某个答案是否是问题Π的解。
2019/5/29 南京航空航天大学 计算机学院

5 10.4 NP完全问题 归约: TT T x T(x) 2019/5/29 南京航空航天大学 计算机学院

6 10.4 NP完全问题 NP完全问题 如果问题Π是NP问题 如果能够在多项式时间内求解问题Π ,那么就可以在多项式时间内求解任何一个NP问题
2019/5/29 南京航空航天大学 计算机学院

7 10.4 NP完全问题 NP完全问题 如果可以找到一个多项式时间的算法A求解某个NP完全问题Π,那么所有的NP问题就可以在多项式时间内求解,也就是说 NP=P 这是个机会? 2019/5/29 南京航空航天大学 计算机学院

8 10.4 NP完全问题 NP完全问题:举例 合取范式(CNF)可满足问题 哈密顿回路问题 顶点覆盖问题 2019/5/29
南京航空航天大学 计算机学院

9 10.4 NP完全问题 如何证明一个问题X是NP完全问题? 证明X是NP问题 证明存在一个已知的NP完全问题Y可以归约到X
2019/5/29 南京航空航天大学 计算机学院


Download ppt "《算法设计技巧与分析》 第10章 NP完全问题 朱友文 zhuyw@nuaa.edu.cn."

Similar presentations


Ads by Google