欢迎大家提Issue反馈问题或建议,建设推理王国!
Skip to content

第19章:复杂度作为推理的几何——为什么有些推理根本无法加速 ​

P≠NP 不是关于机器跑得多快的断言,而是关于问题内在结构的断言。


第18章结尾留下了一个不舒服的观察:即使手里有完整的因果图,在图上做推断——识别因果效应、计算可识别的表达式——在复杂情况下代价也会急剧上升。这不是算法写得不好,而是问题本身就难。

这个"本身就难",需要一个精确的数学含义。

在形式系统的语境里,"难"有一个量化的版本:从公理走到定理需要多少步?第14章提到,验证一个证明可以在多项式时间内完成,但寻找一个证明没有通用的高效算法。这个不对称性在计算理论里有一个正式的名字:P 与 NP 的分离——如果它成立的话。

本章要做的事情,就是把这个"难"的直觉,变成一个精确的几何图景。


19.0 寻找者与验票员游戏:为什么验证比寻找容易 ​

复杂度理论可以从一个非常朴素的游戏开始。

一张金票藏在迷宫里。寻找者的任务是找到它;验票员的任务是检查别人递来的票是不是真的。寻找者可能要在指数级数量的岔道里摸索。验票员却轻松得多:票一到手,他只需检查印章、编号和路径记录是否符合规则。

这就是 P 与 NP 的直觉差别。

如果一个问题属于 P,寻找者自己就能在多项式时间内找到答案。如果一个问题属于 NP,至少当答案为“是”时,有人可以递给验票员一张多项式长度的证书,验票员能够快速确认。

NP 完全问题则更令人畏惧:它们像一座万能迷宫,每一座 NP 迷宫都能被高效地翻译成它。如果你能快速找到这座迷宫里的金票,你就能快速找到每一座 NP 迷宫里的金票。

这个游戏的形式化骨架

  • 状态空间:输入实例 x、候选证书 w、验证器的状态。
  • 合法动作:寻找者生成候选 w;验票员在多项式时间内检查 V(x,w)。
  • 转移规则:搜索过程在候选空间中移动;验证过程按确定性算法扫描证书。
  • 胜利条件:寻找者找到使 V(x,w)=1 的证书,或证明不存在这样的证书。
  • 失败模式:证书很容易检查,但候选空间大到无法穷举;验证快,不代表寻找快。

这个游戏道出了复杂度理论冷酷的一面:难的不是“知道答案之后确认它”,而是“在不知道答案时把它找出来”。证明、规划、SAT、组合搜索——它们全都卡在这个不对称性上。

停机问题把游戏推得更深:有些迷宫并不是太大——问题在于,你根本无法设计出一个总能判断“寻找者会不会走出来”的验票员。那不是 NP 困难,而是可计算性的边界。

验票员游戏最尖锐的地方在于,它羞辱了“事后聪明”。答案摆出来以后,每个人都觉得显而易见;真正的难度藏在答案出现之前。P 与 NP 问的就是:创造和检验之间,是否隔着一道原则性的鸿沟。

19.0.5 用代码玩这个游戏 ​

这座迷宫小到足以穷举。下面的程序在 18 个数字上运行子集和:验票员只需几次加法就能完成验证,而寻找者必须走遍候选空间——并且每一次操作都被计数。

python
#!/usr/bin/env python3
"""
seeker_ticket_checker.py -- the Seeker and Ticket-Checker Game of Ch. 19.
Book reference: The Reasoning Kingdom, Volume 2, Chapter 19, Section 19.0
"The Seeker and Ticket-Checker Game: Why Verifying Is Easier Than Finding."
A golden ticket hides in a maze. The seeker must search corridor after
corridor; the ticket checker only glances at a handed-in ticket. This
program runs the game on a real NP problem, subset-sum:
  * the TICKET CHECKER verifies a claimed subset in linear time,
  * the SEEKER must exhaust candidates -- and we count every operation,
  * a fake ticket gets refused on the spot.
The asymmetry you will see is the cold part of complexity theory: what is
hard is not confirming the answer once you know it, but finding it when
you do not. (NP-completeness: subset-sum is one of the universal mazes
every NP problem can be translated into -- one line here, a chapter in
the book.)
Run:  python3 seeker_ticket_checker.py
"""
from itertools import combinations

NUMBERS = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
TARGET = 128  # = 2 + 7 + 19 + 41 + 59, a sum some subset actually reaches


def verify(numbers, target, ticket):
    """The ticket checker: is this subset a genuine ticket?
    ticket: a tuple of indices. Cost: one addition per element.
    Returns (ok, operations_used)."""
    ops = 0
    total = 0
    for i in ticket:
        total += numbers[i]
        ops += 1
    return total == target, ops


def seek(numbers, target):
    """The seeker: exhaust candidate subsets until one sums to target.
    Returns (ticket, candidates_tried, operations_used). Real, counted."""
    ops = 0
    tried = 0
    for size in range(len(numbers) + 1):
        for ticket in combinations(range(len(numbers)), size):
            tried += 1
            total = 0
            for i in ticket:
                total += numbers[i]
                ops += 1
            if total == target:
                return ticket, tried, ops
    return None, tried, ops


def demo():
    print("=" * 70)
    print(" THE SEEKER AND TICKET-CHECKER GAME -- subset-sum, run for real")
    print(" The Reasoning Kingdom, Volume 2, Chapter 19 (Sec. 19.0)")
    print("=" * 70)
    print(f"\nThe maze: {len(NUMBERS)} numbers, find a subset summing to {TARGET}.")
    print(f"  numbers: {NUMBERS}")

    # The checker's easy life: a real ticket, then a fake one.
    real_ticket = (0, 3, 7, 12, 16)          # 2 + 7 + 19 + 41 + 59
    ok, ops = verify(NUMBERS, TARGET, real_ticket)
    print(f"\nTicket checker, genuine ticket {real_ticket}:")
    print(f"  verdict: {ok}, operations used: {ops}")
    assert ok

    fake_ticket = (1, 4, 9)
    ok, ops = verify(NUMBERS, TARGET, fake_ticket)
    print(f"Ticket checker, fake ticket {fake_ticket}:")
    print(f"  verdict: {ok}, operations used: {ops} -- refused on the spot")
    assert not ok

    # The seeker's hard life.
    ticket, tried, ops = seek(NUMBERS, TARGET)
    print("\nSeeker, searching corridor by corridor:")
    print(f"  candidates tried: {tried}")
    print(f"  operations used:  {ops}")
    print(f"  ticket found:     {ticket}")
    print(f"  check the find:   {verify(NUMBERS, TARGET, ticket)}")
    assert ticket is not None

    print("\nThe asymmetry, in one glance:")
    print(f"  checking the answer cost {len(real_ticket)} additions;")
    print(f"  finding it cost {ops} additions across {tried} candidates.")
    print("  The candidate space has 2**18 = 262144 subsets; the checker")
    print("  never has to look at 262143 of them. That gap is what P and")
    print("  NP are about: creating is not the same job as checking.")
    print("=" * 70)


if __name__ == "__main__":
    demo()

19.1 问题的内在结构 ​

先从一个可能让人意外的区分开始。

有两种“难”,表面相似,本质不同。

第一种:问题很大,数据很多,计算机需要跑很久。这是工程意义上的困难,可以通过更快的硬件、更聪明的算法、更多的并行计算来缓解。这种困难没有原则性的边界。

第二种:无论你用什么算法,无论硬件多快,某些问题就是需要指数级时间。这是数学意义上的困难——不是工程问题,而是问题内在结构的结果。

复杂度理论关心的是第二种。它的问题不是“这个算法快不快”,而是“这个问题能不能被任何算法快速解决”。

很多人听到 P≠NP 就以为“计算机不够快”。这完全错了。P≠NP 说的是:即使给你一台速度无限的计算机,有些问题依然需要指数时间。速度买不来结构。问题的几何形状,不会因为机器变快而改变。

要让“快”有精确含义,需要一个衡量尺度。

时间复杂度:对于输入规模为 n 的问题,最好的算法需要多少步才能给出答案?如果存在一个算法,其步数是 n 的多项式(n2,n3,n100……),就称这个问题是多项式时间可解的;如果每一个已知算法都需要指数级步数(2n,n!,…),那么随着 n 增长,这个问题在实践中会迅速变得不可解。

多项式与指数之间的鸿沟,是复杂度理论的核心分界线。n=100 时,n10=1020 已经大得惊人;2100≈1030,比宇宙中的原子数还多。随着 n 继续增大,这个差距只会变得更加荒诞。

19.1.5 直面数字:多项式与指数的实际含义 ​

把实际数字摆上桌,胜过任何关于“指数爆炸”的抽象谈论。假设每一次操作耗时 1 纳秒(10−9 秒)。

输入规模 nn2(多项式)2n(指数)
10100 ns1 μs
20400 ns1 ms
502.5 μs13 天
10010 μs4×1013 年
20040 μs…

n=100 时,2100 步所需的时间大约是宇宙年龄的 3000 倍。这不是“有点慢”,而是物理上不可能。

但等等——n10 也是多项式。n=100 时,1020 纳秒 ≈ 3171 年。所以多项式不一定快。关键区别在于:多项式的增长被一个固定指数 k 约束(nk),而在指数函数里,增长的是指数本身(kn)。随着 n 增大,多项式总会被指数甩在后面——这是一条渐近分界线,而不是绝对速度的比较。

更重要的是,大多数“自然”出现的多项式时间算法,指数都很小(n,n2,n3,nlog⁡n),而不是 n100。在理论框架里,“多项式”与“指数”之间的边界把握住了“可解”与“不可解”的实践分野——尽管理论承认 n100 是多项式,实践中却没人会用它。


19.2 P 与 NP:两种能力 ​

现在可以定义两个最重要的复杂度类了。

P(多项式时间):所有可以在多项式时间内求解的判定问题的集合。判定问题是一个回答“是”或“否”的问题:这个图有哈密顿回路吗?这个数是质数吗?这个命题在这个逻辑系统里可证吗?

“属于 P”意味着:存在一个算法,对任何规模为 n 的输入,都能在 O(nk) 步内给出正确的“是”或“否”,其中 k 是某个与输入无关的固定常数。

NP(非确定性多项式时间):所有答案可以在多项式时间内验证的判定问题的集合。更精确地说:对每一个“是”的实例,都存在一个多项式长度的证书,可以在多项式时间内被验证。

“属于 NP”意味着:如果答案是“是”,有人能给你看一个简短的证明,而你能在多项式时间内确认这个证明是正确的。

注意这里的不对称性——它正是第14章那个不对称性的回声:验证一个证明是高效的(多项式时间),但寻找一个证明不一定如此(可能需要指数时间)。

P 中的每一个问题都在 NP 中(如果你能在多项式时间内解决一个问题,你当然能在多项式时间内验证一个答案——再解一遍就行了)。问题是:NP 中的每一个问题也都在 P 中吗?

这就是 P=?NP 问题。

严格说来,P ≠ NP 是一个未被证明的猜想。但数十年来,数学家和计算机科学家的经验已经积累成一种强烈的信念:求解与验证之间横着一道根本的鸿沟。如果 P = NP,那么任何可以被快速验证的解,也都能被快速找到——这意味着密码学的崩溃(破解密码和检查密钥一样快),意味着创造力等价于检验,意味着找到一个数学证明和验证一个数学证明之间没有本质区别。那幅图景对我们关于推理和创造的一切直觉都是毁灭性的。对 P ≠ NP 的信念,是“求解比验证更难”这一基本直觉的数学表达。


19.3 NP 完全:最难的问题 ​

NP 中的问题并非全都一样。有些问题具有这样的性质:只要你能快速解决它们,你就能快速解决 NP 中的每一个问题。这类问题被称为 NP 完全。

这个概念需要一件工具:多项式时间归约。如果问题 A 可以在多项式时间内归约到问题 B(记作 A≤pB),意思是:存在一个多项式时间的变换,把 A 的任意实例变成等价的 B 的实例。如果你能快速解决 B,那么通过这个变换,你也能快速解决 A。

多项式时间归约:用“翻译”理解“一样难”

多项式时间归约(A≤pB)说的是:问题 A 不比问题 B 难——你可以用一个高效的“翻译”,把 A 的任意实例变成等价的 B 的实例,然后用 B 的求解器来解 A。

类比:如果你有一本英汉词典(翻译函数),而且你能读中文,那么你就能读英文——英文阅读不比中文阅读更难(在有了词典的前提下)。

NP 完全的含义:如果 C 是 NP 完全的,那么 NP 中的每一个问题都可以在多项式时间内翻译成 C。因此:

  • 如果有人找到了求解 C 的多项式时间算法,那么沿着归约链,所有 NP 问题都能在多项式时间内求解——即 P = NP
  • 如果 P ≠ NP,那么 C 没有多项式时间算法

这就是为什么“解决一个 NP 完全问题”等价于“解决所有 NP 问题”——NP 完全问题是 NP 难度的“代表”。

NP 完全的定义:问题 C 是 NP 完全的,当且仅当:

  1. C∈NP(它的答案可以被快速验证);
  2. 对每一个 A∈NP,都有 A≤pC(NP 中的每一个问题都能归约到 C)。

第一个被证明是 NP 完全的问题,是 SAT(布尔可满足性问题):给定一个布尔公式,是否存在一组变量赋值使该公式为真?Stephen Cook 1971 年的证明——Cook–Levin 定理——是复杂度理论的奠基之作。

SAT 是 NP 完全的,这意味着:如果你能快速判断一个布尔公式是否可满足,你就能快速解决 NP 中的每一个问题——包括旅行商问题、图着色、背包问题……以及,没错,某些因果发现问题。

用形式逻辑的语言说,布尔可满足性问题就是:给定一组命题公式,是否存在一个真值赋值使它们全部为真?这恰好就是寻找模型的问题——逻辑语义的核心操作。第14章说“验证一个证明可以在多项式时间内完成”。这里的对应物是:给定一个候选赋值,检查它是否满足公式,只需把每个值代进去——多项式时间完成。而“寻找”一个使公式为真的赋值,就是 SAT——NP 完全。推理的不对称性在这里获得了精确的计算刻画。

19.3.5 实操:亲手做一个归约(3-SAT → 顶点覆盖) ​

归约不是抽象的概念——它是你亲手可以完成的翻译。下面我们把一个 3-SAT 实例翻译成一个顶点覆盖实例——每一步都可追踪。

源问题:一个 3-SAT 实例:

(x1∨¬x2∨x3)∧(¬x1∨x2∨¬x3)∧(x2∨x3∨¬x3)

三个子句,三个变量。

翻译规则:

  1. 对每个变量 xi,创建一条“变量边”,连接 xi 与 ¬xi(两个顶点)。
  2. 对每个子句,创建一个三角形的“子句构件”——三个顶点,子句中的每个文字对应一个。

目标值 k=|变量|+2×|子句|=3+2×3=9。

构造出的图(节点清单):

  • 变量构件:(x1,¬x1)、(x2,¬x2)、(x3,¬x3),每一对由一条边相连
  • 子句 1 构件:三个节点连成三角形,标为 {x1,¬x2,x3}(子句 1 的三个文字)
  • 子句 2 构件:三个节点的三角形,标为 {¬x1,x2,¬x3}
  • 子句 3 构件:三个节点的三角形,标为 {x2,x3,¬x3}

连线:子句构件中的每个文字节点,都与变量构件中对应的顶点相连。例如,子句 1 的 x1 节点连到变量构件中的 x1;子句 1 的 ¬x2 节点连到变量构件中的 ¬x2。

这个归约为什么有效?(直觉):

  • 要覆盖所有边:对每条变量构件的边,你必须至少选取 {xi,¬xi} 中的一个——这对应于把该变量赋为真或假。
  • 每个子句构件的三角形有 3 条内部边,至少需要 2 个顶点来覆盖——但你选取的变量顶点可能已经“免费”覆盖了子句三角形的一条边(通过连线)。如果子句的某个文字为真,它对应的变量顶点已经覆盖了那条连线边,于是子句三角形只需要再选 2 个顶点。
  • 大小为 k=9 的顶点覆盖存在,当且仅当该 3-SAT 公式可满足。

具体赋值与覆盖之间的对应:取赋值 x1=1,x2=1,x3=1。在变量构件中选取 {x1,x2,x3}(3 个顶点)。子句 1:x1=1 已经覆盖了 x1 的连线边,所以三角形剩下 2 个顶点 {¬x2,x3}——选它们(2 个顶点)。其他子句同理。总顶点数 = 3+3×2=9。✓

这个归约的构造只需要多项式时间:为每个子句画一个三角形,为每条变量边增加两个顶点,把每个子句的文字节点连到对应的变量节点。这一切都能在 O(n+m) 时间内完成(n = 变量数,m = 子句数)。

你刚刚做了什么? 你把一个逻辑问题(“是否存在一组赋值,使这些子句同时为真?”)翻译成了一个图论问题(“这个图是否存在一个不超过 9 个顶点的顶点覆盖?”)。如果你有一个黑盒的顶点覆盖求解器,你就能用它来解 3-SAT——因为你可以把任意 3-SAT 实例翻译成等价的顶点覆盖实例。这就是归约的力量:它不证明某个问题难;它证明的是,如果一个问题容易,那么另一个也容易。

亲手做一个归约,和读一个归约的定义,是完全不同的体验。做过一次之后你会意识到:归约不是抽象的“如果 A 那么 B”——它是一个具体的、可编程的翻译函数。每一条归约都是一个编译器——它把一个问题的语言翻译成另一个问题的语言。NP 完全问题之间的“等价性”不是哲学上的相似,而是你真能跑起来的计算。


19.4 停机问题:比 NP 更深的边界 ​

关于 P 与 NP 的讨论,预设了问题至少能被某个算法回答——只是快慢不同。但还有另一类边界:对某些问题,无论给多少时间,都不存在任何算法能够回答它们。

停机问题:给定一个程序及其输入,这个程序最终会停机,还是会永远运行下去?

图灵在 1936 年证明:没有任何算法能对所有程序正确回答停机问题。

这个证明是经典的自指构造,方法与哥德尔的在本质上相同。

假设存在一个程序 H(P,I),它接受程序 P 和输入 I,并且总能在有限步内正确回答:P 在输入 I 上会停机吗?现在构造另一个程序 D:

D(P)={永远循环若 H(P,P)=停机停机若 H(P,P)=不停机

D 把程序 P 当作自己的输入,问 H:“P 在输入 P 上会停机吗?”——然后做相反的事。

现在问:D 在输入 D 上会停机吗?

  • 若 H(D,D)=停机:那么 D 会永远循环——H 撒谎了。
  • 若 H(D,D)=不停机:那么 D 会停机——H 又撒谎了。

无论哪种情况,H 都给出了错误答案。矛盾。所以 H 不存在。

这个证明的结构,与第15章中哥德尔句 G 的构造完全平行:G 说“我在这个系统中不可证”,D 说“我是 H 判断的反面”。两者都用自指,逼迫任何试图完全刻画自身的系统陷入矛盾。停机问题与不完备定理,是同一枚硬币的两面。

一旦看清这一点,哥德尔和图灵的两个“震撼结果”就变成了同一个结果,只是用两种语言表达。数学的自指与计算的自指,结构完全相同。如果你只是分别背下了这两个定理,你其实还没有真正理解它们。

更精确地说:皮亚诺算术的哥德尔不完备性,可以通过图灵机的停机问题来证明;反之亦然。可计算性理论建立了这一精确对应:一个命题在一个系统中不可判定,当且仅当对应的计算问题不可判定。不完备性不是逻辑特有的现象——它是每一个足够强的形式系统(包括任何通用计算机)共有的内在限制。

停机问题不可判定,意味着存在一道比 NP 完全更深的边界:不是“需要指数时间”,而是“在任何有限时间内都没有算法可用”。复杂度的图景从下往上大致是这样的:

P⊆NP⊆PSPACE⊆⋯⊆可判定⊆可枚举⊊全部问题

停机问题位于“可枚举但不可判定”这一层——你可以在有限步内验证一个停机的程序确实会停机(直接运行它,等它停下来),但你无法在有限步内确认一个不停机的程序永远不会停(你等了一亿步,它还没停——这并不意味着它永远不会停)。

19.4.5 空间与交替:NP 不是故事的全部 ​

除了时间,还有另一个约束:空间(内存)。

PSPACE:所有可以在多项式空间内求解的问题的集合。可以证明 NP⊆PSPACE(你可以在多项式空间内枚举所有可能的证书——用完就回收空间,而不是把所有证书同时存下来)。但 NP 是否等于 PSPACE,至今未知。

PSPACE 中包含比 NP 中任何问题都更难的问题。例如:量化布尔公式(QBF) 是 PSPACE 完全的。QBF 扩展了 SAT:它不只问“是否存在一组赋值使公式为真”,而是问层层交错的量词,比如“∀x1∃x2∀x3… 使公式为真”。这种“交替量词”结构处于复杂度与逻辑的交叉点,对应着多项式谱系——把 NP 的存在量词叠在 coNP 的全称量词之上,每一层(推测上)都比下面一层更难。

多项式谱系(粗略版):

  • Σ1p=NP:∃ 一张证书可以验证该问题
  • Π1p=coNP:∀ 证书,某个条件都成立
  • Σ2p:∃ 一张证书,使得对任意另一张证书,某个条件成立
  • Π2p:对任意证书,∃ 另一张证书……
  • ……以此类推

每一层(推测上)都严格包含下面一层。如果任何一层崩塌(等于下面一层),整座谱系就会崩塌到那一层。例如,如果 NP = coNP,那么 Σ1p=Π1p,由此可以证明整个多项式谱系崩塌到第一层。

这与第15章有什么关系? 多项式谱系的交替量词结构,直接对应逻辑中的证明长度:一个命题包含多少次“对所有”与“存在”的交替,决定了它的证明复杂度处于谱系的哪一层。哥德尔不完备性与复杂度理论正是通过这一对应联系起来的——一个系统的“足够强”,用复杂度的语言说,等价于“能够表达足够多层的量词交替”。


19.5 预言机分离:边界是真实的 ​

一个自然的问题随之而来:P 与 NP 之间的分离,究竟只是我们现有技术的局限,还是一条原则性的边界?

相对化给了我们部分答案。

给算法配上一个预言机(Oracle)——一个能在一步之内回答某一类特定问题的黑盒。根据你选择哪个预言机,P 与 NP 之间的关系可能改变。1975 年,Baker、Gill 和 Solovay 证明了:

  • 存在一个预言机 A,使得相对于 A,PA=NPA;
  • 存在一个预言机 B,使得相对于 B,PB≠NPB。

这个结果的含义是:P ≠ NP 的证明不可能通过相对化来完成。任何基于计数或代数的证明路线,只要它“相对化”(即在预言机模型中仍然成立),就无法区分 P = NP 的世界和 P ≠ NP 的世界。

这并不意味着 P ≠ NP 不可证明——它意味着证明必须是非相对化的:必须深入到计算的本质结构中,而不是停留在算法操作的层面。到目前为止,还没有人满足这个要求。

每一个已知的技术屏障——相对化、自然证明、代数化——都说明同一件事:通往 P ≠ NP 的道路,不经过我们熟悉的任何一条路线。这个问题的深度,也许与它的重要性成正比。


19.6 推理的代价:回到因果 ​

第18章的因果发现问题,现在可以被精确地放进复杂度框架里了。

因果结构学习:给定一组变量上的观测数据,找出与数据一致的因果图。一般情况下——若有 n 个变量,可能的 DAG 数量随 n 超指数增长,穷举搜索根本无从谈起。

已知结果:

  • 在某些限制下(假设因果马尔科夫条件与忠实性条件),PC 算法可以在多项式时间内恢复因果图的骨架(无向边);
  • 但确定边的方向——区分马尔科夫等价类中的不同图——一般情况下是 NP 难的;
  • 存在隐变量时,连骨架都很难恢复。

这些结果说明:精确的因果推断在计算上是根本困难的。不是因为算法写得不好,而是因为问题本身落在 NP 难的范围内。即使数据完美,也没有系统性的办法快速找到答案。

这是对第18章的一记回击:把图给我,我就能做因果推断——但拿到图本身,代价可能超出任何人的支付能力。

因果推断的困境,是推理的一般困境的一个实例:精确推断常常在计算上不可行。这不是算法的问题——它由问题空间的几何形状决定,并且没有捷径。

回到寻找者与验票员游戏:递给它一张候选因果图,很多时候你都能检查它是否满足某些条件独立关系;但在所有可能的 DAG 中找到那张图,是另一个问题。验票员可以快速盖章——这不代表寻找者能快速走出迷宫。第18章给了我们剪线的规则;第19章提醒我们,找到该剪哪张图,本身可能就是一座指数级的迷宫。


19.7 证明与计算的等价 ​

第14章说过:证明是句法对象;验证可以在多项式时间内完成;寻找则不一定。本章把这个直觉变成严格的陈述。

命题逻辑的可满足性(SAT)是 NP 完全的:找到一个使给定公式为真的赋值,与找到一个证明,在计算复杂度上是等价的。

一个更深的对应:证明长度与计算步数。 一个命题在某个系统中的最短证明长度,对应于在某个计算模型下求解相应问题所需的最少步数。证明复杂度正是研究这一对应的领域——它把逻辑系统的表达能力与计算复杂度类连接起来。

一个已知结论:如果存在一个命题证明系统,能为 SAT 的每一个不可满足实例给出多项式长度的不可满足性证明,那么 NP = coNP。换言之:任何足够弱的证明系统,都必然包含这样一些真命题,它们的证明需要指数长度。这不是哥德尔不完备性——它不是说命题不可证;它说的是,即使命题可证,证明也可能长得无法使用。

这是对第14章遗留问题(“证明的长度重要吗?”)的正式回答:是的,极其重要。证明长度是复杂度的镜像,而一个形式系统的表达效率,直接转化为计算问题的难度。


悬而未决 ​

P ≠ NP 是真的吗? 绝大多数人相信如此,但没有人能证明。这是数学中最重要的未解问题之一。如果它是假的——如果 P = NP——那么每一个可以被快速验证的问题都能被快速解决:密码学崩溃,创造力等同于检验,推理的内在代价消失。那个世界与我们的一切直觉相悖,但在逻辑上并不自相矛盾。我们对 P ≠ NP 的信念,比对它的证明更强。

复杂度类的边界是尖锐的吗? P 与 NP 之间是否存在中间地带——既不在 P 中、又不是 NP 完全的问题?Ladner 定理告诉我们:如果 P ≠ NP,那么这样的问题存在,称为 NP 中间问题。图同构问题被怀疑是其中之一,但目前还无法证明。复杂度图景远比 P 与 NP 这两个类丰富。

如果精确推断不可行,近似推断又如何? P ≠ NP 说的是精确解很难找。但也许找到一个“足够好”的近似解,代价要小得多?对某些问题来说确实如此——存在多项式时间的近似算法,能保证解的质量落在最优解的某个比例之内。但对另一些问题,近似同样是 NP 难的——即使允许误差,也逃不掉指数代价。这一区分是第20章的主题:启发式不是随意的近似;它们是由精确数学契约背书的承诺。


思考题 ​

★ 热身

对以下每个问题分类:它属于 P,属于 NP(但不知道是否属于 P),还是不可判定?只需给出分类和一句话理由。

  1. 给定一个有序整数数组和一个目标值,判断目标值是否在数组中(二分搜索)
  2. 给定一个布尔公式,判断它是否可满足(SAT)
  3. 给定一个程序,判断它是否永远不输出任何内容
  4. 给定一个图,判断它是否有哈密顿回路
  5. 给定两个程序,判断它们是否对每一个输入都产生相同的输出

★★ 推导

  1. 归约的方向:如果 A≤pB(A 可以在多项式时间内归约到 B),且 B∈P,那么 A∈P。反过来,如果 A≤pB 且 A 是 NP 完全的,这对 B 意味着什么?考虑两种情况:B∈NP 与 B∉NP。

  2. 停机问题的变体:下面三个停机问题变体中,哪个可判定,哪个不可判定?请清楚说明理由。

    • 给定程序 P 和输入 I:P 是否在 10100 步之内于 I 上停机?
    • 给定程序 P:P 是否在每一个输入上都停机?
    • 给定程序 P:P 是否在某个输入上停机?

★★★ 挑战

第14章说过:验证一个命题逻辑证明是多项式时间可完成的。这意味着“命题逻辑定理验证”——给定一个命题 φ 和一个候选证明序列,判断该序列是否是 φ 的一个合法证明——属于 P。

现在考虑另一个问题:“给定一个命题 φ,判断 φ 是否是定理(即是否存在一个证明)。”

  1. 这个问题属于 NP 吗?(提示:什么充当“证书”?)
  2. SAT 是 NP 完全的,而 SAT 等价于“给定一个命题公式,判断它是否可满足”。在命题逻辑中,“可满足”与“是定理”之间是什么关系?
  3. 把这两件事联系起来:如果 P = NP,这对数学中“寻找证明”意味着什么?如果 P ≠ NP,这是否意味着某些数学定理的证明,即使存在,也原则上永远无法被找到?

第三个问题触及数学哲学中的一个真实问题,目前没有共识答案。试着区分两种情况——“证明存在但找不到”与“证明不存在”——并用本章的语言把这一区分清楚地表述出来。