計算理論導引--時間複雜性(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 歸約為子集和問題
..............................