Class Code: AMC621 Instructor: Huilan Chang
📖 Reference — Introduction to Algorithms (CLRS) by Cormen, Leiserson, Rivest, and Stein // Introduction to the Design and Analysis of Algorithms by Anany Levitin 🏆 S. A. Cook (Toronto Univ., 1971) — proved Cook’s Theorem, received Turing Award（圖靈獎） 🏆 R. Karp (1972) — identified 21 NP-complete problems, received Turing Award 1985
💡 Core Idea 核心想法 The theory identifies a large class of computationally hard problems（計算困難問題） — problems for which no polynomial-time algorithm is known and which are widely believed to require super-polynomial (often exponential) time （指數級） in the worst case — and shows that they are all deeply linked.
Three key observations:
| # | Observation | 說明 |
|---|---|---|
| ① | NP-complete problems share a common trait | 目前無任何多項式時間演算法可解 |
| ② | They are all equivalent in difficulty | 多項式時間解決其中一個 → 多項式時間解決全部 |
| ③ | The theory is about worst-case（最差情況） complexity | 不討論平均情況 |
⚠️ Important — The theory does NOT claim NP-complete problems can never be solved in polynomial time. It only says this is extremely unlikely（極不可能）.
📖 Definition Problems solvable by a deterministic algorithm（確定性演算法） in polynomial time（多項式時間） $O(n^k)$.
Examples:
| Problem | 中文 | Time Complexity |
|---|---|---|
| Linear Search | 線性搜尋 | $O(n)$ |
| Binary Search | 二元搜尋 | $O(\log n)$ |
| Merge Sort | 合併排序 | $O(n \log n)$ |
| Minimum Spanning Tree | 最小生成樹 | $O(E \log V)$ |
| Shortest Path | 最短路徑 | $O(V^2)$ |
📖 Definition Problems whose solutions are verifiable in polynomial time（可在多項式時間內驗證） by a nondeterministic algorithm.
$$ P \;\subseteq\; NP $$
💡 Every P problem is also an NP problem. Most solvable problems one can think of are NP problems.