計算複雜度理論的核心
NP 完全性理論是計算複雜度理論的核心，探討「哪些問題在本質上難以快速解決」。這個理論不僅具有深刻的數學意義，也對密碼學、優化演算法和實際問題的可行性分析有重要影響。計算複雜度理論將問題按照求解所需的資源（如時間、空間）進行分類：從常數時間到指數時間構成複雜度層次。
P 類（Polynomial Time）：所有可以在多項式時間內由確定性圖靈機解決的問題，被認為是「容易解決」的。典型例子包括線性搜尋、合併排序、最短路徑（Dijkstra 演算法）、最大公因數、連通性檢查等。
NP 類（Non-deterministic Polynomial Time）：所有可以在多項式時間內由非確定性圖靈機解決的問題，或等價地，可以由確定性圖靈機在多項式時間內驗證解答的問題。NP 類問題的關鍵特性是：雖然找到解答可能很難（可能需要指數時間），但驗證解答很容易（多項式時間）。
┌─────────────────────────────────────────────────────────────┐ | 複雜度層次 | ├─────────────────────────────────────────────────────────────┤ | | | O(1) 常數時間 陣列存取 | | ↓ | | O(log n) 對數時間 二分搜尋 | | ↓ | | O(n) 線性時間 線性搜尋 | | ↓ | | O(n log n) 線性對數 合併排序 | | ↓ | | O(nᵏ) 多項式時間 P 類 | | ↓ | | O(kⁿ) 指數時間 組合爆炸 | └─────────────────────────────────────────────────────────────┘
NP 完全（NP-Complete）問題是 NP 類中最「難」的問題。任何 NP 問題都可以在多項式時間內歸約到 NP 完全問題。1971 年，史蒂芬·庫克和萊昂尼德·萊文獨立證明了 SAT（布爾可滿足性問題）是第一個 NP 完全問題。
經典 NP 完全問題包括：
| 問題 | 描述 | 應用場景 |
|---|---|---|
| SAT | 布爾公式可滿足性 | 電路設計、規劃 |
| 3-SAT | 每子句恰好 3 個文字的 SAT | NP完全性證明基準 |
| 頂點覆蓋 | 最小的頂點覆蓋大小為 k？ | 網路監控、設施選址 |
| 哈密頓回路 | 存在經過所有頂點的回路？ | 路徑規劃、DNA 測序 |
| 旅行推銷員 | 最短哈密頓回路長度？ | 物流配送、電路設計 |
| 子集和 | 是否存在子集和為目標值？ | 資源分配、貨幣系統 |
| 圖著色 | 圖可用 k 種顏色著色？ | 排程、時隙分配 |
| 背包問題 | 背包價值最大化的選擇？ | 資源優化、投資組合 |
歸約是連接問題難度的橋樑。如果問題 A 可以歸約到問題 B，意味著只要能解決 B，就能解決 A。NP-hard（NP-困難）類包含所有「至少與 NP 問題一樣難」的問題——NP-hard 問題不一定屬於 NP，有些甚至不可計算。
┌─────────────────────────────────────────────────────────────┐ | 問題分類 | ├─────────────────────────────────────────────────────────────┤ | | | P ⊆ NP | | ↓ | | NP ⊆ PSPACE | | ↓ | | PSPACE ⊆ EXPTIME | | | | NP-complete ⊆ NP ∩ NP-hard | | | | 注意：P = NP 仍未解決！ | └─────────────────────────────────────────────────────────────┘
P vs NP 是計算機科學中最大的未解決問題之一，也是千禧年大獎難題之一。若 P = NP，則所有 NP 問題都有多項式時間演算法，密碼學將被徹底顛覆。若 P ≠ NP（多數人相信），則 NP-Complete 問題本質上困難，密碼學有理論安全保障。
在實際應用中，面對 NP 完全問題的策略包括：特殊情況處理、參數化演算法、近似演算法（如頂點覆蓋的 2-近似演算法）、隨機演算法等。