前言
P 与 NP 用来描述解决问题所需的时间的难度为：polynomial time 或 non-deterministic polynomial time。
将问题分类为 P 或 NP，有助于理解一个问题是否有可能在合理的时间内被解决——即执行时间不会随着输入规模的增长而爆炸性膨胀。历史上有许多原本只知道属于 NP 的问题，后来被找到了多项式时间的算法，从而被证实其实也属于 P 问题，像是：质数判定。但目前没有证据可证明所有 NP 问题是 P 问题。
P vs NP
- P 问题
- 可快速解决
- 快速验证
- NP 问题
- 不确定能否快速解决
- 快速验证
快速在这里指「问题能不能处理任何输入时在 polynomial time 时间内被解决」，像是 Big O 表示来说：
- 常数时间：O(1)
- 对数时间：O(log n)
- 线性时间：O(n)
- 线性对数时间：O(n log n)
- 平方时间：O(n²)
- 立方时间：O(n³)
P 问题示例：排序
给定 [3, 1, 4, 1, 5, 9]，排序由小到大。
- 解决：直接用排序算法（例如 归并排序），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)。
Reducibility 归约
如果问题 A 可以转换成问题 B，那 B 至少跟 A 一样难
想象你有一台完美的翻译器（归约函数），能将「法文问题 (A)」转换为「英文问题 (B)」：
因为只要有翻译器，任何法文问题都能变成英文问题来解；所以只要能解英文问题，就等于能解所有的法文问题，代表英文问题的难度涵盖了法文问题。
# A 可以在「polynomial time」內轉歸約為 BA ≤p BNPC NP-Complete
NP 当中最难的问题
- 是 NP 问题
- 任何一个 NP 问题，都可以在 polynomial time 内归约成这个问题的形式
要厘清 P 是否等于 NP 可以透过解决 NP-Complete 问题来得出答案，因为所有 NP 问题都能 Reduce 为 NPC。
NP-Complete 问题示例：SAT（Boolean Satisfiability Problem）
所有 NP 問題 ≤p SAT
有没有一种 A、B、C 的 true/false 组合，能让整个公式成立？
(A ∨ ¬B) ∧ (¬A ∨ C) ∧ (B ∨ ¬C)- 解决：最坏情况下需要枚举所有 2ⁿ 种组合，没有已知的 polynomial time 解法。
- 验证：给定一组指派，代入计算即可在 O(n) 内确认。
总结
P = NP? 在于「能快速验证答案」 是否等同於 「能快速找到答案」？