第4卷第9章坚强、正直、美丽

从强正美柔逻辑题进入SAT、3-CNF、P与NP，再完整分析RANDOM-WALK-3-SAT：用汉明距离、单侧错误、二项式定理、钢琴路径和斯特林公式把指数底从2降到1.334。

学习目标

能用真值表、字面量和 3-CNF 说明 SAT 的“满足/不可满足”以及有限例子为什么会指数爆炸
能解释随机漫步如何用汉明距离把高维分配空间投影成一维，并推导单步靠近概率至少为 1/3
能区分 SAT 证据的确定性正确与 probably UNSAT 的单侧错误，并用独立重启控制失败概率
能比较 1.5ⁿ 与 1.334ⁿ 的路径计数来源，检查二项式定理、斯特林公式和指数底的推导

从八个条件开始：为什么“看起来简单”仍可能极难

本章从四个日常形容词开始，却通向计算机科学最著名的未解决问题之一。局部上，一个三字面量子句只需让其中一项为真；整体上，许多子句互相牵制，找到同时满足它们的分配可能需要探索指数规模的空间。

先预测：

四个真假变量只有16种分配，为什么把变量数扩大到34就会出现171亿7986万9184种？
从一个不满足的三字面量子句随机翻转变量，为什么至少有1/3概率更接近某个正确分配？
算法返回“可以满足”为什么绝不会错，返回“大概无法满足”却可能错？
只计“笔直走向答案”得到1.5ⁿ，把绕路也算进去为什么反而能把上界改进到1.334ⁿ？

9.1 家

雨天的周六

又一个雨天周六，尤里却与上一章相反，兴高采烈地来到房间。原因藏在她带来的信封里，但她先递出一道“强正美柔问题”。

令四个分别表示：

S=\text{坚强},\quad R=\text{正直},\quad B=\text{美丽},\quad G=\text{温柔}.

八个条件是：

\begin{aligned} P_1&=S\lor R\lor B,\\ P_2&=G\lor R\lor\neg B,\\ P_3&=\neg S\lor G\lor B,\\ P_4&=\neg S\lor\neg G\lor R,\\ P_5&=\neg G\lor\neg R\lor B,\\ P_6&=\neg S\lor\neg R\lor\neg B,\\ P_7&=S\lor\neg G\lor\neg B,\\ P_8&=S\lor G\lor\neg R. \end{aligned}

问题是：是否存在一组S、R、B、G的真假值，使八个条件同时为真？

“我”先尝试逻辑推导。假定坚强，再由不同条件推出温柔、正直、美丽，最后却与P₆冲突；改从不坚强出发，也会在另一条件卡住。但试过几条推理路线都失败，仍不能证明不存在答案。

四个变量共有：

2^4=16

种。把16行全部列出并逐一检查P₁到P₈，每一行都恰有一个条件为假。因此：

P_1\land P_2\land\cdots\land P_8

不可满足。更精巧的是，删除任意一个Pᵢ，都存在一行满足剩余七项；八个条件中没有冗余。

有限例子可以完整覆盖四变量分配；删除一条子句的测试说明八个条件没有冗余。

题目并非尤里原创，而是转学男生在回信中出的。她抱怨对方回信太慢、内容还是数学题，脸上却藏不住高兴。上一章等待回信的随机摇摆，在这一章以新的数学对话落地。

9.2 图书室

9.2.1 逻辑题

放学后，泰朵拉听说尤里收到回信，比当事人还高兴。她相信语言可以让心意互通。米尔嘉与理纱随后来到图书室，“我”把强正美柔问题讲给大家听。

米尔嘉没有把它只看成16行小题，而是立刻认出背后的：日常形容词只是变量名字，真正结构是“能否为变量赋值，使整个逻辑公式为真”。

9.2.2 可满足性问题

英文是Satisfiability Problem。直接枚举当然总会结束，但“能算完”不等于“高效”。

若公式有n个变量，全部分配有：

2^n

种。所谓高效，在这里指运行步数可由n的某个固定次幂控制，也就是：

O(n^K)

而不是指数阶O(2ⁿ)。变量数从4增到34时：

2^{34}=17\,179\,869\,184.

这正是第3章标题里的171亿7986万9184。有限并没有阻止指数爆炸。

9.2.3 3-SAT

Satisfiability 缩写为 SAT。先分层建立术语：

x₁、x₂、...是变量；
¬是；
变量x或否定变量¬x叫；
用“或”连接若干字面量得到；
用“且”连接多个子句得到；
每个子句恰有三个字面量的CNF叫。

例如：

(x_1\lor\neg x_2\lor\neg x_3) \land (x_2\lor x_3\lor\neg x_4)

是。判断一个3-CNF是否存在满足分配的问题叫 SAT。

9.2.4 满足

当分配a使公式f为真，就说a``f。3-CNF整体为真，当且仅当每个子句都为真；只要有一个子句为假，整体就为假。

这一区分非常重要：

“公式可满足”表示至少存在一个满足分配；
“这个分配满足公式”表示给定分配验证为真；
“公式不可满足”表示所有分配都失败。

强正美柔问题就是由8个三字面量子句组成的3-CNF不可满足性问题。

9.2.5 分配方式的练习

短公式可以凭观察找出满足分配，但算法必须处理任意长度输入。最直接的枚举2ⁿ种分配，最坏情况直到最后一项才找到答案，或全部检查后确认无解。

对4个变量只是16种，对34个变量已超过170亿。理纱用“低效”概括问题：指数底数看似只是2，变量每增加1个，工作量却翻倍。

9.2.6 NP完全问题

可以高效求解。关注的是高效验证候选，而不是已经知道如何高效找到候选。

NP不是Not Polynomial，而是Nondeterministic Polynomial time。所有P问题都是NP问题，但是否：

P=NP

仍未解决。多数研究者相信P≠NP，但未经证明仍只是猜想。

具有关键地位：若任何一个NP完全问题被证明属于P，就有P=NP。SAT是历史上第一个被证明NP完全的问题。给定一个分配，检查公式是否为真很快；怎样快速找到满足分配，或证明不存在，仍没有已知的一般多项式算法。

9.3 回家路上

9.3.1 誓言与约定

四人走向车站。泰朵拉谈起亲戚婚礼上的誓言，“无论生病还是健康”让她感动。“我”想起米尔嘉深夜电话里的话：约定是表明决心。数学问题要求明确条件，人生的选择也要求说出自己愿意承担的方向。

9.3.2 会议

米尔嘉再次问泰朵拉是否愿意在双仓图书馆会议上报告。泰朵拉仍害怕，但当“我”说也许会有初中生因她的报告第一次遇见算法，她决定接受：有人愿意听，就应该为听众认真整理思想。

理纱在会议秘书处帮忙，提醒宣传单仍印着米尔嘉的名字。米尔嘉当天会在美国，计划更改必须真正传达到执行方。这里把“想传递”推进到“对听众、时间和协作负责”。

9.4 图书室

9.4.1 求解3-SAT问题的随机算法

第二天，米尔嘉与理纱完成一个版本。输入为3-CNF公式f、变量数n与重启轮数R：

RANDOM-WALK-3-SAT(f, n, R)
  repeat R rounds
    a <- uniformly random assignment of n variables
    repeat at most 3n steps
      if a satisfies f
        return SAT with assignment a
      c <- any clause of f not satisfied by a
      x <- a uniformly random variable occurring in c
      flip x in a
  return probably UNSAT

外层做R次随机重启，内层每轮最多走3n步。只有重启时从全体2ⁿ分配中随机选起点；轮内每一步都受当前不满足子句引导。

9.4.2 随机漫步

每个分配是n维布尔立方体上的一个点，相邻点只差一个变量。算法先随机落到一个点，再反复翻转一个变量，所以它在2ⁿ个分配组成的空间里做随机漫步。

关键不是随便翻转。若当前分配a不满足某个三字面量子句c，则c的三个字面量在a下全为假。假设公式确实可满足，并固定某个满足分配a*。在a*下，c至少有一个字面量为真，因此三个相关变量中至少一个在a与a*之间不一致。

从三个变量中均匀选一个翻转，至少有：

\frac13

概率翻中不一致变量。局部动作可能让别的子句变坏，但相对固定的a*，它至少有1/3概率靠近一步。

算法不知道正确分配在哪里，但分析者固定一个 a*，用汉明距离把高维路径投影到一维。

9.4.3 向着定量评估前进

算法并不知道a*是什么，所以运行时无法观察自己究竟在接近还是远离。但分析者可以固定任意一个满足分配作为参照，并给出概率边界：

\Pr(\text{接近一步})\ge\frac13, \qquad \Pr(\text{远离一步})\le\frac23.

“不知道当前方向”不妨碍“知道方向概率”。这正是随机算法分析的转换：不追踪每次具体选择，而约束大量可能运行的总体行为。

9.4.4 另一个随机漫步

两个等长真假向量中不同位置的数量叫。记：

d(a,a^*)= \#\{j:a_j\ne a_j^*\}.

若距离为0，a=a*，公式已满足。一次变量翻转只改变一个位置，所以距离只能：

m\longmapsto m-1 \quad\text{或}\quad m\longmapsto m+1.

高维分配空间中的随机漫步，由汉明距离投影成一条数轴上的一维随机漫步。靠近概率至少1/3，远离概率至多2/3。

9.4.5 关注循环

把内层3n步视为一轮。要估计总运行时间，先估计。

算法输出“可以满足”时，同时给出可验证分配，因此不会误报；输出“大概无法满足”时，可能只是没有走到答案。这叫。

若单轮成功率至少为M⁻ⁿ，独立运行：

R=K M^n

轮后仍全部失败的至多：

\begin{aligned} \left(1-\frac1{M^n}\right)^{K M^n} &\le \left(e^{-1/M^n}\right)^{K M^n}\\ &=e^{-K}. \end{aligned}

这里用到1+x≤eˣ。增大常数K会指数降低疏忽概率，而指数底仍由Mⁿ决定。

随机性影响的是找证据的机会；一旦证据出现，确定性检查负责保证正确。

9.5 家

9.5.1 幸运的评估

夜里，“我”独自分析。随机起点a与固定正确分配a*距离为m，意味着恰有m个变量不同。起点均匀随机，因此：

p(m) = \Pr(d(a,a^*)=m) = \frac1{2^n}\binom{n}{m}.

先只计算最幸运路线：从距离m开始，连续m次都靠近。每步靠近概率至少1/3，所以：

q(m)\ge\left(\frac13\right)^m.

因为m=0,1,\ldots,n的起点事件互斥且覆盖全部起点，单轮成功率至少：

\sum_{m=0}^{n}p(m)q(m) \ge \frac1{2^n} \sum_{m=0}^{n} \binom{n}{m} \left(\frac13\right)^m.

9.5.2 化简和式

二项式定理：

\sum_{m=0}^{n}\binom{n}{m}x^m =(1+x)^n

取x=1/3：

\begin{aligned} \Pr(\text{单轮成功}) &\ge \frac1{2^n} \left(1+\frac13\right)^n\\ &= \left(\frac23\right)^n. \end{aligned}

这里同时使用了两种概率结构：不同起始距离事件彼此，所以对m求和；连续翻转选择按随机步骤相乘，后面会用独立性解释。

9.5.3 次数的评估

单轮成功率至少(2/3)ⁿ，其倒数是(3/2)ⁿ。令：

R=K\left(\frac32\right)^n,

疏忽概率至多e⁻ᴷ。暴力算法指数部分为2ⁿ，幸运粗估把它降为：

1.5^n.

这不是说算法必定在1.5ⁿ步内找到答案，而是以可调错误概率换取更小的指数底。

9.6 图书室

9.6.1 独立与互斥

第二天，“我”把1.5ⁿ结果讲给伙伴们。米尔嘉区分两个容易混淆的概念。

事件A、B时：

\Pr(A\cap B)=\Pr(A)\Pr(B).

事件A、B互斥时：

\Pr(A\cup B)=\Pr(A)+\Pr(B).

独立用于连续随机选择的概率相乘；互斥用于不同起始距离的概率相加。除非某事件概率为0，否则互斥事件通常不独立。

9.6.2 精确的评估

幸运粗估只计算从距离m连续靠近m次的直线路线，丢掉了“先远离再回来”的成功路径。现在计入远离i步的路线。为了补偿这i步并消除原有距离m，必须靠近m+i步，总步数：

m+2i.

限制0≤i≤m，总步数最多3m≤3n，这也解释内层循环为何取3n。

距离不能低于0，路径计数与第8章左右翻转后一一对应。令钢琴一般解中的：

(a,b)=(m+i,i),

合法路径数是：

\frac{m}{m+2i} \binom{m+2i}{i}.

每条路线包含i次远离和m+i次靠近。用最坏偏置硬币估计：

P(m,i) \ge \frac{m}{m+2i} \binom{m+2i}{i} \left(\frac23\right)^i \left(\frac13\right)^{m+i}.

对0≤i≤m求和，令从距离m最终到达0的概率下界为Q(m)：

Q(m) \ge \sum_{i=0}^{m} \frac{m}{m+2i} \binom{m+2i}{i} \left(\frac23\right)^i \left(\frac13\right)^{m+i}.

利用i≤m：

\frac{m}{m+2i}\ge\frac13, \qquad \left(\frac23\right)^i\ge\left(\frac23\right)^m, \qquad \left(\frac13\right)^{m+i}\ge\left(\frac13\right)^{2m}.

因此：

Q(m) \ge \frac13 \left(\frac2{27}\right)^m \sum_{i=0}^{m}\binom{m+2i}{i}.

和式各项非负，所以至少不小于最后一项：

\sum_{i=0}^{m}\binom{m+2i}{i} \ge \binom{3m}{m}.

于是：

Q(m) \ge \frac13 \left(\frac2{27}\right)^m \binom{3m}{m}.

直冲终点只有一条模式；现在钢琴路径把大量绕路成功方式都计入，因此下界会更高。

9.6.3 斯特林公式

是：

n! \sim \sqrt{2\pi n} \left(\frac ne\right)^n.

原章使用配套界：

\sqrt{2\pi n}\left(\frac ne\right)^n \le n! \le \sqrt{2\pi n}\left(\frac ne\right)^n e^{1/(12n)}.

把：

\binom{3m}{m} = \frac{(3m)!}{m!(2m)!}

的分子用下界、分母用上界，可整理为：

\binom{3m}{m} \ge \frac{C}{\sqrt m} \left(\frac{27}{4}\right)^m,

其中：

C=\frac{\sqrt3}{2\sqrt\pi}e^{-1/8}

是与m、n无关的正常数。代回：

\begin{aligned} Q(m) &\ge \frac13 \left(\frac2{27}\right)^m \frac{C}{\sqrt m} \left(\frac{27}{4}\right)^m\\ &= \frac{C'}{\sqrt m} \left(\frac12\right)^m, \end{aligned}

其中C'=C/3。

再按随机起点距离求和。把m=0单独处理，并用1/√m≥1/√n：

\begin{aligned} \Pr(\text{单轮成功}) &= \sum_{m=0}^{n} \frac1{2^n}\binom{n}{m}Q(m)\\ &\ge \frac{C'}{\sqrt n} \frac1{2^n} \sum_{m=0}^{n} \binom{n}{m} \left(\frac12\right)^m\\ &= \frac{C'}{\sqrt n} \left(\frac34\right)^n. \end{aligned}

所以重复次数最多需要多项式因子乘：

\frac{\sqrt n}{C'} \left(\frac43\right)^n.

比较指数部分：

\left(\frac43\right)^n =(1.333\ldots)^n <1.334^n.

粗估的1.5ⁿ降到1.334ⁿ。√n/C'并未消失，只是在比较指数阶时不支配增长。

绕路不是噪声：把合法路径完整计数，组合数增长可以抵消一部分单步概率损失。

伙伴们画出评估“旅行地图”：固定起点距离，借钢琴问题数路径，转成抛硬币概率，求Q(m)，用斯特林公式估计组合数，再对初始距离使用二项式定理。泰朵拉意识到，武器不仅是公式，还包括判断何时求上界、何时求下界的方向感。

离馆前，大家抢在瑞谷老师之前齐声宣布放学，理纱也小声加入；老师仍按自己的节奏重复原句。高强度推导在这个小小恶作剧里收束。

9.7 回家路上

奥林匹克

泰朵拉追问为什么每轮恰是3n步。若起点距离为m、途中远离i≤m步，总步数为m+2i≤3m≤3n，所以精确分析计入的路径都能在一轮内走完。

随机起点、检查满足性、选择子句等步骤仍需时间，但假设它们都可在输入规模的多项式时间内完成；决定指数竞争的是重启轮数。

泰朵拉把降低3-SAT指数底比作奥林匹克纪录。研究者提出算法、证明边界、发表论文，后来者继续改进。米尔嘉所读的是乌韦·舍宁1999年的A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems；当时3-SAT纪录的指数部分是1.334ⁿ。论文的本质是规范、正确地写下值得传达的结果。

9.8 家

逻辑

周末，尤里戴着回信中得到的新缎带，再次与“我”谈可满足性。她发现不仅可以解问题，还可以把“设计更快算法”本身变成问题，也就是研究问题的问题。

逻辑公式转成概率、不等式、组合数与渐近估计，说明数学主题并不孤立。尤里听说理纱能理解二进制斐波那契手势，又得知双仓图书馆会议有面向中学生的研讨会，立刻意识到自己也能参加。她嘴上担心泰朵拉在台上摔倒，实际已经在期待新的对话。

本章没有解决P与NP，却给出一种面对难题的可靠姿态：先把对象定义清楚，再设计算法、量化成功概率、控制错误、比较增长阶，并把证明写到别人能够复查。

概念证据索引：从公式标记回到可复查对象

以下锚点把真值表、随机漫步、路径估计和叙事现场重新接回推理。数学记号与代码标记有时会把一个概念切成几段，这里用完整短语明确它们的角色。

S∨R∨B / G∨R∨¬B / ¬S∨G∨B / ¬S∨¬G∨R：四个正负字面量组成的子句，分别检验不同布尔变量组合。
¬G∨¬R∨B / ¬S∨¬R∨¬B / S∨¬G∨¬B / S∨G∨¬R：另外四个子句与前四个一起构成强正美柔的八条件公式。
与P₆冲突：一条逻辑推导若推出 P₆ 为假，就说明该分支不能继续，但还不足以覆盖全部分配。
2⁴=16 / 删除任意一个Pᵢ / Sixteen-Assignment Table / Remove-One-Clause Test：16 行有限真值表和删一条子句测试分别检查不可满足性与无冗余性。
有限例子 / 覆盖了四变量的全部16种分配：小规模穷举能完成覆盖，但不能直接推出一般 SAT 的高效算法。
n个变量 / O(nᴷ) / 17 179 869 184：多项式与指数的规模差异在 34 个变量时已经可见。
非运算 / 变量x / 否定变量¬x / 逻辑或 / 逻辑且：¬、变量、∨ 和 ∧ 是把日常命题编码为 CNF 的基本词汇。
枚举2ⁿ种分配 / 工作量翻倍：每增加一个布尔变量，直接枚举的候选数翻倍。
多项式时间归约 / Formula Construction Ladder / Find-versus-Verify Audit / NP不是Not Polynomial：复杂度分类需要归约和求解/验证区分，NP 不是“非多项式”的字面缩写。
Schöning / 局部随机搜索：Schöning 的思路用局部随机搜索降低 3-SAT 的指数底。
3-CNF公式f / 变量数n / 重启轮数R / R次随机重启 / 3n步：随机算法输入包含公式、变量规模、重启次数和每轮步数。
2ⁿ个分配 / n维布尔立方体 / 三个字面量全为假：每个分配是立方体顶点；选择不满足子句时，三个字面量都为假。
固定某个满足分配a* / 至少一个字面量为真 / 至少一个变量不一致：分析者固定参照解 a*，保证当前不满足子句的三个变量中至少一个需要翻转。这里也明确记作 固定某个满足分配a*。
算法并不知道a / 最少翻转次数 / d(a,a)**：算法不看见正确解，分析用 d(a,a*) 表示到它的最少翻转次数。
靠近概率至少1/3 / 远离概率至多2/3：从不满足三子句中均匀挑变量，至少三分之一机会降低距离。
内层3n步 / 循环的成功概率 / 单侧错误蒙特卡罗算法：把固定步数作为一轮，并把只可能漏解的输出保证单独命名。
R=KMⁿ / 增大常数K / Assignment Hypercube Walk / One-Sided Output Check：重启次数和两个图示共同说明路径与失败概率的控制。
完整随机抽样只发生在每轮起点 / 局部引导：重启从全空间抽样，轮内则由不满足子句局部引导。
随机起点a / 正确分配a* / 连续m次都靠近 / (1/3)ᵐ：幸运粗估从随机起点连续下降到 a*；参照解也可写作 正确分配a*。
m=0,1,...,n / R=K(3/2)ⁿ / 暴力算法指数部分为2ⁿ：按全部初始距离求和后，粗估的重复次数指数部分为 1.5ⁿ；距离求和的范围明确是 m=0,1,...,n。
Pr(A∩B)=Pr(A)Pr(B) / Pr(A∪B)=Pr(A)+Pr(B)：独立事件相乘，互斥事件相加，条件不同不能混用。
远离i步 / 靠近m+i步 / 总步数m+2i：绕路 i 步后必须靠近 m+i 步，总长度是 m+2i，也就是 总步数m+2i。
m/(m+2i)≥1/3 / (2/3)ⁱ≥(2/3)ᵐ / (1/3)ᵐ⁺ⁱ≥(1/3)²ᵐ：在 0≤i≤m 下分别控制合法路径比例和两项概率因子。
ΣC(m+2i,i) / n!∼√(2πn)(n/e)ⁿ / 阶乘的渐近公式：路径总和和阶乘渐近共同把组合计数转成指数下界；渐近式的紧凑写法是 n! \sim \sqrt{2\pi n}。
(3m)!/(m!(2m)!) / C=√3e⁻¹⁄⁸/(2√π) / m=0单独处理：组合数常数、斯特林界和零距离边界都要在严格估计中保留；常数也记作 C=√3e⁻¹⁄⁸/(2√π)，即 C=√3e⁻¹/⁸/(2√π)。

Distance-Path Correspondence / Exponent-Base Ledger：两个复盘图分别追踪距离到路径、概率到指数底的账本。
判断何时求下界 / 放学时间到了：研究者既要会放松估计，也要知道何时下界足以支撑结论；高强度推导仍有结束时刻。

互动实验与四步复盘

猜一猜：把随机漫步从“只计直冲”改为“计入绕路”，指数底会变大还是变小？再切换到证据检查，观察概率错误和确定性验证的边界。

3-SAT Walk Lab

切换分析视角，观察路径、指数底和正确性保证的关系。

当前视角：完整路径

关键结论：低于 1.334ⁿ

计入远离后返回的钢琴路径。

分步1 / 4

1. 真值表：从有限例子建立问题

列出四变量的 16 行，标记每行违反的条件，再运行删一条子句测试。