文档介绍：P NP NPC NP-hard问题
HPNL
1
并不是表示一个程序解决问题需要花费多少时间,而是指当问题规模扩大后,程序需要的时间长度增长得多快。
例如:
时间复杂度
2
多项式级的复杂度
非多项式级的复杂度
时间复杂度
3
根据求解问题所需的时间复杂度划分
P问题(Polynomial)
NP问题(Non-Polynomial)
NPC问题(plete)
NP-hard问题
P NP NPC NP-hard的划分
4
判定问题
答案为yes或no
优化问题
答案为极值,不能单纯地用yes或no来判定
判定问题与优化问题
5
可以在多项式的时间里解决的问题则是P问题
P是单词多项式polynomial的简写
例子
给定几个数,让从小到大排列
给定几个数,查找最大值
P问题(Polynomial)
6
定义一
可以在多项式时间内验证一个正确解的问题
定义二
可以在多项式时间里猜出一个正确解的问题
由定义可知
所有的P问题都是NP问题,那反之呢?
最著名的“NP”问题
证明或推翻P=NP
NP问题(Non-Polynomial)
7
标准定义
如果能够找到这样一个变化法则,对于任意一个程序A的输入,都能按照这个法则变换成程序B的输入使得两程序的输出相同,则,问题A可归约为问题B。
分析
问题A能归约为问题B,指,可以用问题B的解法来解决A
例如:一元一次方程可以归约为一元二次方程
B的复杂度大于或等于A的复杂度,即,问题A不比B难
传递性
若问题A可以归约为问题B,问题B可以归约为问题C,则问题A可以归约为问题C
归约(Reducibility)
8
定义
它是一个NP问题
所有的NP问题都可以归约到它
同时满足以上两个条件的即为NPC问题
传递性
P问题可以归约为NP问题,NP问题可以归约为NPC问题
NPC问题(plete)
9
定义
所有的NP问题都可以归约到它
即NP-hard问题的定义满足NPC问题定义的第二条但不一定要满足第一条
NP-hard问题要比NPC问题的范围广
NP难问题(NP-hard)
10