前言
P 與 NP 用來描述解決問題的難度所需的時間為：polynomial time 或 non-deterministic polynomial time。
將問題分類為 P 或 NP，有助於理解一個問題是否有可能在合理的時間內被解決——即執行時間不會隨著輸入規模的增長而爆炸性膨脹，歷史上有找到用 P 來解決 NP 問題的方法過，像是：質數判定。但目前沒有證據可證明所有 NP 問題是 P 問題。
P vs NP
- P 問題
- 容易解決
- 容易驗證
- NP 問題
- 難以解決
- 容易驗證
容易與困難在這裡指「問題能不能最快在 polynomial time 時間內被解決」，像是 Big O 表示來說：
- 常數時間：O(1)
- 對數時間：O(log n)
- 線性時間：O(n)
- 線性對數時間：O(n log n)
- 平方時間：O(n2)
- 立方時間：O(n3)
- …
P 問題範例：排序
給定 [3, 1, 4, 1, 5, 9]，排序由小到大。
- 解決：直接用排序演算法（例如 merge sort），O(n log n)。
- 驗證：掃一遍確認每個數 ≤ 下一個數，O(n)。
NP 問題範例：子集合加總（Subset Sum）
給定 [3, 7, 1, 8, 5]，有沒有某個子集合的總和恰好等於 14？
- 解決：試遍所有子集合，有 2ⁿ 種可能，只要輸入 n 一大就爆炸。目前沒有已知的 polynomial time 解法。
- 驗證：假設是 [1, 5, 8]，只要運算一下：
1+5+8=14，O(n)。
NP-Complete
要釐清 P 是否等於 NP 可以透過解決 NP-Complete 問題來得出答案，NP-Complete 定義如下：
- 是 NP 問題
- 任何一個 NP 問題，都可以在 polynomial time 內轉換成這個問題的形式
NP-Complte 問題範例：SAT（Boolean Satisfiability Problem）
有沒有一種 A、B、C 的 true/false 組合，能讓整個公式成立？
(A ∨ ¬B) ∧ (¬A ∨ C) ∧ (B ∨ ¬C)- 解決：最壞情況需要枚舉所有 2ⁿ 種組合，沒有已知的 polynomial time 解法。
- 驗證：給定一組指派，代入計算即可在 O(n) 內確認，屬於 polynomial time。
總結
P = NP? 在於「能快速驗證答案」 是否等同於 「能快速找到答案」？