计算机数学入门（五）：验证很快，找到很难

上一篇：（四）机器算不出来的东西——讲有些事机器根本做不了。 这一篇：讲有些事机器能做，但可能永远做不完——这是"能不能算"和"算得快不快"的分界。

注：大 O 和复杂度的基础（增长阶、为什么 O(n²) 不等于慢）已经在 /cs/analysis/ 讲过，这一篇不重复，只讲它没讲的那块——P vs NP。

耗时：读完约 45 分钟，动手约 1.5 小时。

开头：验一下答案只要 1 纳秒，找出答案要试 320 亿次

先做一个实验。给定两个 11 位质数：

p = 32416190071
q = 32416187567

问题一：验证。 “这两个数相乘等于 N 吗？”

p * q == N        # 一次乘法

耗时：3,338 纳秒。 一瞬间。

问题二：找出。 “反过来，只给你 N，找出它的两个质因数。”

试除法要从 2 开始一个个试：

需要试除：32,416,190,071 次（试到第一个因子 p）

这两个问题的难度差了 300 亿倍。 而且 N 越大，差距越悬殊——你银行卡用的 RSA 加密，N 有 617 位十进制，找它的因子要试大约 10³⁰⁰ 次，宇宙终结都试不完。

但验证这个 617 位数的因子，依然只要一次乘法。

这一篇讲的就是这件事：「验证一个解」和「找到一个解」是两个完全不同的难度等级。 而这两者到底差多少、会不会其实一样——是计算机科学里最重要的未解问题，价值 100 万美元。

一、先分清两件完全不同的事

这是大多数人（包括很多程序员）一辈子没分清的概念：

数独是最干净的直觉：

• 验证：给你一张填好的数独，你一行一行、一列一列、一宫一宫查过去，几分钟就验完。这是"检查"。
• 找解：给你一张空数独，让你填出来。这是"求解"。

验证和求解，是两件事。 大部分人觉得"反正都要做"，但数学上它们差着天壤之别。

二、实测：子集和问题

用代码把这两件事的差距量化出来。

子集和问题：给你一堆数，能不能挑出几组，加起来正好等于目标值 S？

验证一个解：给你一组"挑或不挑"的选择，你把这些数加一遍，看等不等于 S。这是 O(n)——加 n 个数而已。

暴力找解：从 0 到 2ⁿ−1 枚举每一种选择，每种算一遍和。这是 O(2ⁿ)。

实测（数字本机随机生成）：

n=50 时，验证依然 0.01 毫秒，找解要 12.9 天。

再往上：

n=60：找解 ≈ 37 年
n=100：找解 ≈ 4×10^13 年（宇宙年龄才 1.38×10^10 年）

而 n=100 时，验证一个解，还是 0.01 毫秒。

这就是"验证"和"找"的本质区别：一个随 n 线性增长，一个随 n 指数爆炸。

三、SAT：另一个同样残酷的例子

SAT（可满足性）是更"正宗"的例子，因为它是第一个被证明 NP 完全的问题。

SAT 问的是：给一个布尔公式（一堆"且、或、非"），能不能给变量赋值让它变成真？

验证一个赋值：代入公式算一遍。快。

暴力找赋值：枚举 2ⁿ 种赋值。慢。

实测：

变量数从 20 涨到 22，找赋值从 0.7 秒跳到 12 秒。 验证始终 0.03 毫秒。

四、P 和 NP：两个名字，一道分水岭

现在把上面的直觉形式化。

P：能"快"找到解的问题

P = 存在多项式时间算法，能从零找到解。

“多项式时间"就是代价是 n^k 这种（n²、n³、n log n 都算）。P 是"求解也快"的问题。

例子：排序、最短路径、素数判定、最大公约数。

NP：能"快"验证解的问题

NP = 存在多项式时间算法，能验证一个给定解对不对。

注意：NP 不要求"找到"快，只要求"验证"快。

例子：子集和（验证 O(n)）、SAT（验证 O(变量数)）、数独、旅行商。

P 和 NP 的关系

P ⊆ NP   这是显然的：能找到解，当然也能验证解。

关键问题：反过来成立吗？

P = NP 吗？

如果 P = NP：“验证快"就意味着"找到也快”。 子集和、SAT、数独……全都有多项式解法。

如果 P ≠ NP：“验证快"不等于"找到快”。 有些问题验证容易、找极难。

没人知道答案。 这是克莱数学研究所（Clay）悬赏 100 万美元 的 7 个"千禧年难题"之一，从 1971 年 Cook 提出至今，半个世纪无人解决。

五、为什么 P vs NP 不是一个，是几千个

这里有个惊人的事实：那一大堆"验证快、找难"的问题，其实是同一个问题。

它们叫 NP 完全问题（NP-complete）。家族部分成员：

• SAT（可满足性）——第一个被证明的，Cook 1971
• 子集和、背包
• 旅行商（TSP）、图着色、哈密顿路径
• 数独、拼图
• 蛋白质折叠（某些模型）

关键性质：这些问题可以互相"多项式时间归约”。 意思是：如果你能快速解其中任意一个，你就能快速解全部。

所以：

找到一个 NP 完全问题的多项式解法 → P = NP → 全部都被攻破
证明一个 NP 完全问题没有多项式解法 → P ≠ NP → 全部都没救

“P vs NP” 是一个问题，不是几千个问题。 它们是被一条归约链串成的一整片。

这解释了为什么全世界的数学家和计算机科学家都在同一个问题上使劲——因为解一个，就解了所有。

六、你的密码，押在 P ≠ NP 上

这是这一篇最"切身"的一节。

RSA 加密（你每次打开 HTTPS 网站、刷银行卡都在用）的安全性，建立在两件事上：

1. 验证因子快：给两个质数 p、q，乘起来得到 N，一次乘法。
2. 找因子慢：只给 N，反推 p、q，试除法要 10³⁰⁰ 次。

如果 P = NP 被证明是真的（有人找到多项式分解算法）：

你的 HTTPS、银行卡、密码、加密货币，全部在数学意义上"可被快速攻破"。

注意：P = NP 的证明本身不直接等于"给出破解算法"，但它意味着理论上存在多项式算法，而历史证明"存在"往往很快变成"找到"。

如果 P ≠ NP（大多数人相信，但没证明）：

验证快、找慢这件事，是结构性的、永恒的，不是"暂时没找到好算法"。密码学就有了坚实的立足之地。

所以你现在每一次安全的网络交易，都押注在"P ≠ NP"这个尚未被证明的猜想上。 你手机里的加密，不是建立在"黑客暂时没想到办法"上，是建立在"数学上可能根本没有快办法"上。

七、多项式 vs 指数：为什么分水岭在这

为什么"多项式"和"指数"是那条线？看增长率的本质区别：

关键区别在"n 翻倍时"：

• 多项式（n²）：n 翻倍 → 代价乘 4（一个常数）。数据翻倍，慢一点点。
• 指数（2ⁿ）：n 翻倍 → 代价平方。数据翻倍，直接爆炸。

n=10 → 2^10 = 1024
n=20 → 2^20 = 1,048,576  （= 1024²）

这就是为什么多项式是"可解的代名词"，指数是"不可行的代名词"。

这不是数学家的洁癖，是真实计算能力的物理边界：多项式的机器能应付数据增长，指数的机器会被数据增长碾压。

（注意：这有个重要的补充——“多项式"不代表"快”，n¹⁰⁰ 也是多项式，但实际不可行。复杂度理论是渐近的，讲的是"n 很大时"的趋势，不是"n=100 时"的秒表。这一层在 /cs/analysis/ 里已经点过，这里不展开。）

八、把这一篇放回体系

五篇讲完，八层目录已经走完前五层：

四、五两篇的关系（这个递进值得记住）

注意这是三个等级，不是两个：

1. 能快算（P）——排序、最短路径
2. 能算但可能算不完（NP 难）——子集和、SAT、数独
3. 不能算（不可判定）——停机问题、有没有 bug

大多数人的认知停在"能算/不能算"两层，漏掉了中间那层"能算但算不动"。 中间那层，恰恰是密码学、人工智能、优化、运筹学的全部战场。

九、动手：五个实验

实验 1：验证 vs 找（子集和）

import random, time, itertools

def 暴力找(nums, S):
    n = len(nums)
    for mask in range(1 << n):
        if sum(nums[i] for i in range(n) if mask >> i & 1) == S:
            return mask
    return None

def 验证(nums, mask, S):
    return sum(nums[i] for i in range(len(nums)) if mask >> i & 1) == S

random.seed(11)
for n in [15, 20, 25]:
    nums = [random.randint(1, 100) for _ in range(n)]
    S = sum(nums) // 2
    t = time.time(); sol = 暴力找(nums, S); find = time.time() - t
    t = time.time(); ok = 验证(nums, sol, S); ver = time.time() - t
    print(f"n={n}: 找 {find*1000:.1f}ms | 验证 {ver*1000:.6f}ms | {ok}")

注意"找"那一栏随 n 暴涨，而"验证"始终是 0.00x ms。

实验 2：亲眼看指数爆炸

for n in [10, 20, 30, 40, 50, 60]:
    print(f"n={n:2d}: 2^n = {2**n:,}")
# 看到 2^60 已经 1.15×10^18，而验证还是 n 步

实验 3：验证一个 50 元素的解，瞬时

import random, time
random.seed(2)
n = 50
nums = [random.randint(1, 1000) for _ in range(n)]
mask = random.getrandbits(n)
S = sum(nums[i] for i in range(n) if mask >> i & 1)

t = time.time()
ok = sum(nums[i] for i in range(n) if mask >> i & 1) == S
print(f"验证 n=50 的解: {ok}, {(time.time()-t)*1e6:.1f} 微秒")
print(f"暴力找 n=50 的解: 2^50 ≈ 12.9 天")

实验 4：SAT 验证 vs 找

import itertools, time, random

def 验证赋值(clauses, assign):
    def ok_clause(c):
        return any((lit > 0 and assign[abs(lit)-1]) or
                   (lit < 0 and not assign[abs(lit)-1]) for lit in c)
    return all(ok_clause(c) for c in clauses)

def 暴力找(clauses, nvar):
    for bits in itertools.product([0,1], repeat=nvar):
        if 验证赋值(clauses, list(bits)): return bits
    return None

r = random.Random(42)
nv = 18
clauses = [[v if r.random()<0.5 else -v for v in r.sample(range(1, nv+1), 3)]
           for _ in range(nv*4)]

t = time.time(); sol = 暴力找(clauses, nv); print(f"找: {(time.time()-t)*1000:.1f} ms")
t = time.time(); print(f"验证: {验证赋值(clauses, list(sol))}, {(time.time()-t)*1000:.6f} ms")

实验 5：你的密码押在 P ≠ NP

# 验证因子快、找因子慢
p, q = 32416190071, 32416187567
N = p * q
import time
t = time.time(); ok = (p*q == N)
print(f"验证 p×q==N: {ok}, 一次乘法 {(time.time()-t)*1e9:.0f} 纳秒")
print(f"只给 N 找因子: 试除要 {p} 次（试到第一个因子）")
print("RSA-2048: N 有 617 位，试除要 ~10^300 次")

十、带走的东西

一句话：

「验证一个解」和「找到一个解」是两个难度等级——前者往往一纳秒，后者可能宇宙都算不完；而这俩到底差多少，就是价值 100 万美元的 P vs NP 问题。

三句话：

1. P = 能快找到解，NP = 能快验证解。 P ⊆ NP 显然；P = NP 吗，半个世纪没人知道。
2. NP 完全问题是一个，不是几千个——SAT、子集和、背包、数独、旅行商互相归约，解一个就解了全部。
3. 你的密码押在 P ≠ NP 上。 RSA 的安全性 = “验证因子一纳秒，找因子 10³⁰⁰ 次”。如果哪天 P = NP 被证明，你的 HTTPS 和银行卡在数学上就"可快速攻破"。

一个最该记住的认知升级

复杂度不是两层（能算/不能算），是三层：

1. 能快算（排序）
2. 能算但算不动（数独、SAT）
3. 不能算（停机问题）

中间那层，是密码学、AI、优化、运筹的全部战场。

下一篇

（六）不确定的世界：概率、贝叶斯、随机化。

从一个反直觉的问题开始：99% 准确率的检测，测出阳性，你有病的概率其实不到一半。 然后是贝叶斯定理、随机化算法为什么反而更可靠、以及为什么"随机"是计算机里最有用的工具之一。

深水区

• 复杂度理论主干：Sipser《Introduction to the Theory of Computation》后半部分，P/NP/NP 完全/归约。
• NP 完全原始论文：Stephen Cook, The Complexity of Theorem-Proving Procedures（1971）。第一个 NP 完全证明。
• 千禧年难题：Clay 数学研究所官网的 P vs NP 问题陈述（官方、免费）。
• 好懂的普及：Scott Aaronson 的博客和《Quantum Computing since Democritus》，讲 P vs NP 讲得又深又清楚。

这些我不做页码引用——不同版本页码不同，写了就是骗你。按书名和章节找。

附：本篇所有数字的来源

全部本机跑出来：Ubuntu / Python 3.8 / x86-64。

子集和（验证 vs 找）：

• n=15/20/25/30 暴力找解 5.1 / 5.1 / 79.2 / 50.6 ms
• 验证一个解 0.007 / 0.006 / 0.013 / 0.013 ms
• n=50 验证 11.4 微秒；暴力找 2⁵⁰ ≈ 12.9 天（1e9 步/秒）
• n=60 找 ≈ 37 年；n=100 找 ≈ 4×10¹³ 年（宇宙年龄 1.38×10¹⁰ 年）

SAT（3-SAT，变量数 10/15/20/22）：

• 暴力找赋值 1.5 / 19.8 / 734.7 / 12301.1 ms
• 验证一个赋值 0.017 / 0.024 / 0.034 / 0.037 ms

RSA 因子：

• p=32416190071, q=32416187567, N 乘积
• 验证 p×q==N：一次乘法，约 3,338 纳秒
• 试除找因子：32,416,190,071 次（试到第一个因子 p）
• RSA-2048：N 有 617 位十进制，因子 300 位质数，试除约 10³⁰⁰ 次

增长率：n=10/20/40/60 时 n² 与 2ⁿ 的对照表（n=60 时 2⁶⁰ = 1.15×10¹⁸，n²=3600）。

事实性内容（非实测，来自公开知识）：BB 值、Cook 1971、Clay 悬赏 100 万美元、NP 完全问题列表、RSA 机制——这些是教科书级的既定事实。

你自己机器上跑出来的数字会略有不同。差一点不影响结论——结论是结构性的。