快速找到
存在一个算法，让求解时间随输入规模多项式增长。不是「一瞬间」，而是不会随规模爆炸。
P VS NP · 判断与寻找
等号
一个尚未写下的等号
P 是「能快速找到解」的问题；NP 是「能快速验证解」的问题。 P = NP 问的是：如果答案一旦被给出，你可以很快检查它，那么你是否也总能很快找到它？
P ⊆ NP 是确定的。等号是否成立，至今没有人证明，也没有人推翻。
快速验证
给出一个候选解，存在一个算法在多项式时间内检查它对不对。每个 P 问题都在 NP 里。
同一类吗
如果 NP 里的每个问题都能被快速求解，等号成立。这是理论计算机科学最著名的开放问题。
01 / SUBSET SUM
选一组数，让和刚好等于目标。
这是 P vs NP 的日常形状：验证一个候选解，只要把选中的数加一遍； 找到它，却要在 216 个子集里搜索。
目标和
—
16 个数 · 65,536 个子集
已选
0
还没选
等待一个候选解
—
点数字选中它。检查是即时的。
SEARCH SPACE
216 = 65,536
还没有开始搜索。
已检查 0
每个小格 = 一个子集
02 / THE EXPONENTIAL WALL
每多一个数，世界就多一倍。
验证始终只需要 n 次加法；暴力搜索要试 2n 个子集。 拖动滑杆，看这两条线怎样分开。
- 验证一个解
- —
- 暴力搜索
- —
- 按每秒 10 亿次
- —
- 对比
- —
n = 10n = 90
横条按对数刻度画，所以它看起来不像指数——数字会提醒你它是。
03 / IF THE EQUALS SIGN HOLDS
世界会松动，但不会免费。
假设某天有人证明了 P = NP，并且给出了算法。这不是魔法，但一些被认为 「只能碰运气」的事会变成「可以计算」的事。
会松动的
- 公开密钥。RSA、椭圆曲线依赖「分解 / 离散对数很难」。等号成立意味着这些搜索也有高效算法。
- 规划与优化。路线、排班、装箱、芯片布线——很多都是 NP 问题，搜索会变成计算。
- 科学与工程。蛋白质折叠、药物设计、自动定理证明：把「猜一个结构再验证」变成「直接算」。
不会自动发生的
- 多项式不等于实际快。常数和次数可能巨大，理论上的 O(n100) 也救不了今天的电脑。
- 只覆盖 NP。不是所有难题都在 NP 里；更高复杂度的问题不因此自动变容易。
- 算法可能仍未知。P = NP 说明存在，不说明我们今天就能把它写出来。
- 密码学还看平均情况。最坏情况的等号，不是全部故事。
多数研究者相信 P ≠ NP；但信念不是证明。
04 / BOUNDARIES
它不是什么。
- 不是一个证明。这页只是把 P vs NP 的一个侧面做成可玩的模型。
- 暴力搜索只是最笨的算法。没找到多项式算法，不等于它不存在——这正是问题所在。
- 时间按每秒 10 亿次估算。忽略常数、并行和硬件；真实的门槛只会更复杂。
- 验证快不等于找到快。这两件事之间那条没有画上的等号，就是全部悬念。
这个模型怎么搭的
问题。子集和（subset sum）是 NP 完全问题：给定一组整数和目标，是否存在一个子集，其和恰好等于目标。候选解是一个子集，验证只需 O(n) 次加法；暴力搜索有 2n 个子集。
实例。页面生成 16 个互不相同的整数，并挑一个只对应唯一子集、且在枚举顺序里靠后的目标和。搜索矩阵有 65,536 个格子，正好对应 216 个子集。
估算。「每秒 10 亿次」只是把 2n 换算成人类尺度的标尺；宇宙年龄按 138 亿年计。P = NP 的部分全部是条件句，不是已知事实。
代码。规则与动画在 js/pnp.js，样式在 css/pnp.css。没有使用任何机器学习或图论库。