计算理论导引--时间复杂性(PPT 109页)

引言
主要内容
度量复杂性
渐进分析
大 O 和小 o记法
大 O 和小 o 记法
大O 和小o 记法
分析算法
时间复杂性类
分析 M2 的时间复杂性
分析M3的时间复杂性
A 的 C 程序
总结 A 的运行时间
复杂性理论与可计算性理论的区别
模型间的复杂性关系
多项式时间
P中的问题举例
P中的问题举例--PATH
PATH∈P
P中的问题举例-- RELPRIME
RELPRIME∈P
P中的问题举例--上下文无关语言
NP 类
多项式可验证性
NP类
判定 HAMPATH
NP中问题举例—CLIQUE
NP中问题举例—SUBSET-SUM
关于 NP 中问题的说明
P 与 NP 问题
NP完全性
NP完全性—可满足性问题
多项式时间可归约性
3SAT
示例：从 3SAT 到 CLIQUE
NP完全性定义
库克-列文定理
几个NP完全问题
顶点覆盖问题
哈密顿路径问题
子集和问题
子集和问题--从 3SAT 到 pSUBSET-SUM 的归约
Subset Sum
设合取式满足，可选出xi yi如下其和为最后一行，对应一个子集和
不满足加不够3
Proof 3SAT P Subset Sum3SAT 归约为子集和问题
..............................