P vs NP

P vs NP 是计算机科学里最重要的问题之一，也是千禧年大奖难题之一。

• P：可以在多项式时间内求解

• NP：可以在多项式时间内验证
• NP-complete：既属于 NP，也是 NP-hard（NP 中最难的问题）
  • SAT、3-SAT、3-coloring...
  • Cook Levin 定理证明了 每个 NP 问题都可以规约到 SAT
• NP-hard：至少和 NP 中最难的问题一样难，但它自己不一定属于 NP

如果为 NP 问题找到一个 “P” 解法，会发生什么？

假设：private -> public 很容易，但 public -> private 不可能。一个实用的 NP 解法会打破这个前提。

• Bitcoin、SSH 都依赖 public key <-> private key 机制

• 花钱时：

message = "Spend this coin to Carol, with this fee"
signature = Sign(private_key, message)

• 验证时：

Verify(public_key, message, signature) == true

问题规约

$a \leq b$

$a$ 可以规约到 $b$，意思是：“如果我们能解决 $b$，我们就能解决 $a$。”

比如 $a$ 是“在一组数字里找到第 k 大的元素”，$b$ 是“给一组数字排序”。如果我们能解决 $b$，那就能很容易解决 $a$。

例子：Vertex Cover 和 Independent Set

哲学含义

判断是否比创造更容易？ 搜索也许是智能的本质 知识不等于被压缩后的知识

知识不只是压缩后的产物。 知识也包括解压、重建、使用它的能力。