NP完全性学习笔记
1、易解与难解
- 易解问题：有多项式时间算法
- 难解问题：不存在多项式时间算法
已证明难解的问题：
a.不可计算的问题 图灵1936停机问题：输入+程序，是否会停机
b.有算法但至少需要指数或更多时间和空间
既没有多项式时间算法，又未证明是难解的问题
•哈密顿回路 货郎 背包
2、判定问题与优化问题
- 判定问题：回答是与否的问题。
k独立集 售货员问题（长度不超过D）
- 优化问题：构造一个解使目标函数最大或最小
最大独立集 售货员（最短路）
3、P与NP
P类：所有多项式时间可解的判定问题组成的问题类
EXP类：所有指数时间可解的判定问题组成的问题类
NP：所有多项式时间可验证的判定问题组成的问题类
4、确定型与非确定型
5、P与NP
6、NP-完全
7、NP-完全问题的性质
8、NP完全问题的解题策略
9、典型的NP完全问题：m着色问题、旅行商TSP问题。
10、
