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

第24章:NP 问题的探讨——LIT 定理 ​


AL 集合;AL 居民:1L

XL=(AL,&,|,!) 半环

(XL,d) ⇒ 空间

路线:定义空间与距离 → 构造迭代列 → 除法 → 换底进入对数空间 → 取 n→∞ → 用「离散空间里没有 −∞」导出矛盾 → 证离散性引理 → 显式构造 P 居民 → 反证 NP 居民不存在 → 回到理想时间,给出上界。

前言:先穷举,再说收敛 ​

一个子句,三个变量。字面量怎么排、插什么值、插什么算子、加什么条件,读到最后都是同一件事:这组取值下,子句满不满足。除此之外,它没有别的行为。

所以不去猜它的结构,只列它的行为。三个变量各取 0 或 1,八种取值;一组取值一个答案,八个答案就是一张完整的表。把这张表从头到尾穷举出来,一条不漏。

八个答案不分开跑。把它们叠在一起,收进同一条变量 an,按理想时间 n=0,1,2,… 往前推。每推一步,整叠答案一起更新。理想时间不回溯、不改错,只沿着成功的那条路走,这一叠就被一层一层叠出来。

这一步之后,收敛性是一个可以算的问题。an 落在空间 XL 里,两点之间的距离是汉明距离——数有几个取值不同。T 每推一步压掉多少距离,直接算(§2)。

这办法不神秘,甚至很蠢:不懂子句的结构,就把取值全试一遍。可讲朴素不动点,就得用这个蠢办法。聪明一点的方法一上来就假定了结构,朴素性就没地方站。蠢办法把整个空间填满;填满了,不动点落在哪一格,才谈得下去。

1. 空间 ​

1.1 值集合 AL(平凡基础) ​

对每个 L,定义平凡值集合

AL:={0,1}L∪{&,|,!}

|AL|=2L+3。AL 只做两件事:装 L 位状态,装三个逐点算子。平凡居民取常一状态

1L:=(1,…,1)∈{0,1}L⊆AL

到空间上就是常一值函数 1XL。

1.2 构造 A3 与完备空间 ​

取 L=3:A3:=AL|L=3,由 8 个状态和 3 个算子组成,共 11 个:

编号状态
0(0,0,0)
1(0,0,1)
2(0,1,0)
3(0,1,1)
4(1,0,0)
5(1,0,1)
6(1,1,0)
7(1,1,1)
8&
9|
10!

X3 是值函数空间:元素 f:D→A3 是值函数,&、|、! 对它逐点作用。

3-SAT 情形取 D={0,1}n。值函数就是求值映射:

Φ:{0,1}n→A3

n=3 时 D 有 8 个状态;|A3|=11,所以 X3=A3D 有 118 个值函数。可满足 ⇔ Φ 不是常零函数——在空间里是「非零函数」这个子集,形态是一个锥 / 超平面,里面没有子句语法。

X3=A3D 是完备空间:距离见 1.4,完备性见 1.5。

1.3 构造 A2 与完备空间 ​

取 L=2:A2:=AL|L=2,由 4 个状态和 3 个算子组成,共 7 个:

编号状态
0(0,0)
1(0,1)
2(1,0)
3(1,1)
4&
5|
6!

2-SAT 情形取 D={0,1}2,X2:=A2D 是完备空间:距离见 1.4,完备性见 1.5。

L=2:2-SAT,∈P;L=3:3-SAT,NP 完全(Cook–Levin)。

1.3.1 不是 3 位/2 位填表,而是整个解空间沿时间轴迭代 ​

A2、A3 不是「输入只有 2 位或 3 位」。它们是逐点枚举的值集合:AL 把 {0,1}L 的每个状态都枚举进去,XL=ALD 再把所有候选值函数包进同一个空间。

  • D={0,1}3 枚举 8 个候选输入状态;X3=A3D 是整个候选解空间。
  • 迭代对象 an∈X3 不是单个 3 位赋值,而是整张候选表:8 个状态的值同时被包在 an 里,沿时间刻度 n 一起演化。
  • 时间门只数「恰好 3 个满足状态」:satStates(an)=3 时,整个空间才允许推进到 an+1;否则时间停住,无法往外推。

所以「3」是当前时间片上恰好满足的 3 个状态,不是输入长度;「2」同理,最多只有 2 个满足状态,变不出第 3 个,3-时间门永远关闭。

1.3.2 最优时间:只计成功推进 ​

回溯、改错、踌躇不前的分支不进时间账。只记录真正过门、成功向前的步骤:

ReachesIn f0 0 f0ReachesIn f0 (n+1) g若 ReachesIn f0 n f 且 stepSpace f=some g

IsOptimalTime f0 goal n 取的是最短成功路径的步数;失败分支和改错时间被归约掉,不计入 n。

1.3.3 离散时间与神级机器(绝对最优时间) ​

时间取离散刻度 n=0,1,2,…。状态空间不是单条轨迹,而是整个 XL 被包在 an 里一起演化。

Oracle 时间(神谕时间)是一个名词:它指没有任何改错、完全贴着状态空间成功路径演化的最理想时间。它不是新增的物理机器,也不是额外的计算能力;它只是给这个最理想时间起的名字。设想一个神谕(oracle)作为这个理想演化者:每一步都完全贴着状态空间里成功的那条路径走,失败、回溯、改错的分支根本不进入时间账。它的时间定义成

OracleRun f0 goal n⟺∃ state:N→X3state 0=f0state n=goal∀i<n, stepSpace (state i)=some (state (i+1))

OracleOptimal 再要求它是所有成功路径中最短的:

OracleOptimal f0 goal n=OracleRun f0 goal n∧∀m, ReachesIn f0 m goal→n≤m

这个 n 是绝对最优时间:

  • 上界:确实存在一条 n 步成功路径(神谕到了);
  • 下界:任何成功路径都不短于 n;
  • 回溯、改错、踌躇不前的时间全部归约掉,不计入 n。

它是神谕的时间,不是任何物理机器的实际时间;物理机器只能比它慢。

1.4 加权汉明距离 ​

空间是离散的:AL 是 2L+3 个元素的有限集,D={0,1}L 是 2L 个状态的有限集,XL=ALD 是有限积。空间里没有方向、线段和内积,欧几里得距离不是它自身的度量;坐标结构给出的度量必须是汉明型——逐坐标比较,数不同的坐标:

d(f,g)=|{x∈D: f(x)≠g(x)}|

几何性质:

  • 取值为整数 0,1,…,|D|;
  • 相邻即「恰好一个坐标不同」,d(f,g) 是有限积图上的最短路径长度;
  • 单位权时,以 f 为心、半径 r 的球是「至多 r 个坐标不同」的函数集,是子立方体的并。

加权汉明在每个坐标上乘权重 wx≥0:

dw(f,g)=∑x∈Dwx⋅1[f(x)≠g(x)]
  • 度量的汉明型由离散性决定,权重不改变这个型
  • wx≡1 ⇒ 普通汉明距离
  • 一般值集合:dw(f,g)=∑x∈Dwx⋅δ(f(x),g(x)),δ 为 A3 上的离散度量

3-SAT 情形(D={0,1}n):

dw(f,g)=∑x∈{0,1}nwx⋅1[f(x)≠g(x)]

n=3 时求和跑完 8 个状态;n=2 时求和跑完 4 个状态。

范数形式(A3={0,1}):

∥f∥w=∑x∈Dwx⋅f(x)dw(f,g)=∥f⊕g∥w

1.5 完备性 ​

  • AL 是值集合,XL 是值函数空间,&、|、! 逐点作用。
  • 逐点结构 ⇒ 完备性按坐标继承:XL 是每个输入坐标上一份 AL 的积。XL 是半环 / 格 / 有补 ⇔ AL 是;XL 完备 ⇔ AL 完备。
  • 度量侧:加权汉明是逐坐标聚合。输入集有限 ⇒ XL 有限 ⇒ 柯西完备自动成立;无限时,XL 的完备性由 AL 的距离完备性决定。
  • 表达侧:{&,|,!} 逐点生成 AL 上的函数代数;能生成全部值函数,靠的是 AL 本身是布尔值集。

一句话:这个值函数空间的完备性是继承来的——AL 完备它就完备,AL 缺什么它就缺什么。

2. 迭代列 ​

2.1 最朴素的单变量迭代 ​

迭代对象不是单个值,也不是单个变量 X1,X2,…,而是把全部状态收进同一个集合变量:

  • 所有值集合
  • 所有状态
  • 所有变量的全部取值方式

全部包进 an,让它按时间 n 往前迭代;每一步把集合里的状态全部取到,这是穷举性质的迭代。所谓「单变量」,指的就是这一个包住全部状态的集合变量。

在完备空间 (X,d) 上构造迭代列:

an+1=T(an)

迭代条件:

d(T(an),T(an+1))≤qn⋅d(an,an+1)

证明它确实是柯西列。这条证明只用一个事实:距离是整数,而且只有有限多个可能的取值。

记 δn:=d(an,an+1)。迭代条件就是

δn+1=d(an+1,an+2)≤qnd(an,an+1)=qnδn

因为 0≤q<1,所以 qn≤1,于是

δn+1≤δn

相邻两项的距离一路不增。

先看第一格。δ0=d(a0,a1) 是汉明距离:数的是 a0 与 a1 有几个坐标不同。空间上一共 |D| 个坐标,所以

d(an,an+1)=δn≤δ0≤|D|

L=3:|D|=8,δ0 是 0 到 8 的整数。L=2:|D|=4,δ0 是 0 到 4 的整数。

再紧一格。n≥1 时 qn<1,所以只要 δn>0,就有 δn+1<δn——一次至少掉一格,没有平局。整数只减不增,掉 δ0 格就到地板:

δn≤δ0−(n−1)(1≤n≤δ0+1)

取 N=δ0+1:L=3 时 N≤9,L=2 时 N≤5。于是 δN=0,从这一项起

aN=aN+1=aN+2=…

序列不再动,是常列。常列是柯西列,极限就是这个点;所有 m,n≥N 的 d(am,an)=0。

拿 11 验一遍:A3 是 8+3=11 个值,X3 有 118 个点,这条路却在十步之内走完。

加权汉明是同一本账,只是每一格的价钱不同:dw(an,an+1)≤dw(a0,a1),距离落在有限个值里,一格格掉下去,有限步也到底。

2.2 迭代条件的除法形式 ​

记

Δn:=d(T(an),T(an+1))δn:=d(an,an+1)

把迭代条件右边的乘子除到左边:

Δnδn≤qn
  • 左边:像的距离 Δn 除以原像的距离 δn
  • 右边:指数函数形式
  • 0≤q<1

为什么要把乘子除到左边?Δn 和 δn 都是距离,量纲相同;它们的商是一个纯数,衡量的是 T 在这一步把距离压掉了多少倍。qn 也是纯数。两个纯数比大小,跟距离取什么单位无关。写成乘积 Δn≤qnδn 意思一样,但倍数的意思被乘法藏住了;除法把它摆到明面上。

除法也把假设写在了分母上:只有当 δn>0、序列还在往前挪的时候,Δn/δn 才是一个数。序列一旦冻结,an=an+1,分子 Δn=d(an+1,an+2)≤qn⋅0=0 也为 0,比值退化成 0/0——不是大,不是小,是没有定义。所以除法形式只覆盖「还在动」的那一段。这一点进对数空间以后会原样出现。

3. 对数空间 ​

3.1 换底公式 ​

换底公式:

logb⁡x=logc⁡xlogc⁡b

把真数替换为分子 Δn,底数替换为分母 δn:

logδn⁡Δn=logc⁡Δnlogc⁡δn

除法不等式换到对数空间:

ln⁡(Δnδn)≤n⋅ln⁡q⟺ ln⁡Δn−ln⁡δn≤n⋅ln⁡q
  • 指数形式 qn 在对数空间变成线性项 n⋅ln⁡q
  • 除法式与换底公式同构:分子 Δn ↔ 真数,分母 δn ↔ 底数

换底公式本身就是一次除法。分子是真数,分母是底数;§2.2 的比值和对数刻度上的商是同一件事,写成减法就是 ln⁡Δn−ln⁡δn。

连乘变连加只靠一条性质:ln⁡(xy)=ln⁡x+ln⁡y。所以 qn 在对数坐标里不是「看起来像」一条直线,它就是一条直线:每推一步,坐标往下平移 |ln⁡q|;推 n 步,往下平移 n|ln⁡q|。在对数坐标 y 上看,这一步的映射是

y↦y+n⋅ln⁡q

缩放换成了平移。而 nln⁡q 作为 n 的函数是一次函数:过原点,斜率 ln⁡q 是定数,n 走多远它就走多远。指数在对数空间里没有剩下弯曲,只剩这项线性项和它的斜率。

3.2 真分数 ​

0≤q<1 ⇒ ln⁡q<0。于是

ln⁡Δn−ln⁡δn≤n⋅ln⁡q<0

即 Δn<δn:这个比值是一个真分数。

3.2.1 为什么这一项会走到 −∞ ​

右边的 nln⁡q 是 n 乘一个定数,ln⁡q<0,所以每走一步就往下掉一个固定的量 |ln⁡q|。步数没有尽头,间距不变,它就穿过每一个实数往下走,没有地板;任何有限的上界都拦不住它,只能记作 −∞。

左边被 ≤ 拴在右边下面。右边没有底,左边的上界也就没有底,跟着掉。

左边本来有别的去处。ln⁡Δn−ln⁡δn 是两个距离的对数之差,而距离只取有限个值:无权的场合是整数 0,1,…,|D|,加权的场合是有限个非负数。非零时它的对数是某个有限的数;对数只把一个距离送到 −∞,就是 0:

ln⁡0=−∞

所以左边的全部可能值是一个有限集,再加上 −∞ 这一个点。有限集里挑不出一个数,能一直待在 nln⁡q 下面;能一直跟到底的只有 −∞。极限因此把不动点记在坐标的尽头:对数空间没有比它更低的槽位。

3.3 取极限 ​

令 n→∞:

limn→∞(ln⁡Δn−ln⁡δn)≤limn→∞n⋅ln⁡q=−∞

上界跑到 −∞,所以:

  • 极限在 −∞
  • 不动点也在 −∞

4. 矛盾 ​

但这个空间是离散空间,没有 −∞ 这一项。

一边不动点在 −∞,一边空间里没有 −∞:

⇒ 前后矛盾,直接证伪。

5. P 居民与 NP 反例 ​

以下结论都在 §1 的离散空间 (X,d) 内。

5.1 离散性引理 ​

X=A3D,|D|=8,|A3|=11,故 |X|=118 有限。加权汉明距离只取有限个值,令

δmin:=min{d(f,g): f,g∈X, d(f,g)>0}>0

设 {an} 是柯西列。取 N,使 m,n≥N 时 d(am,an)<δmin。于是

d(am,an)=0(m,n≥N)aN=aN+1=aN+2=…

即柯西列的极限是 X 中的一个具体点 a∗。

5.2 LSAT 与 P 居民 ​

LSAT:每个子句恰好 L 个字面量。

  • L=2:2-SAT,∈P;
  • L=3:3-SAT,NP 完全(Cook–Levin)。

这里要把这条铁链说清楚。3-SAT 是 NP 难的,这件事不是我们构造出来的。准确说,它是 NP 完全的:既在 NP 里,又是 NP 难的。这个结论比这本书早:Cook(和 Levin)证明了,NP 里的每个问题都能在多项式时间内规约到 SAT;SAT 再到 3-SAT,只做两件机械的事——把长子句拆成三个字面量的子句(必要时加辅助变量),把短子句用重复字面量补齐。两段接起来,NP 里的每个问题都规约到 3-SAT。链子是别人焊好的,3-SAT 被拴在末端,NP 难是链子给它的性质,不是我们这一步给它的性质。

我们在这里构造的是空间和居民,不是 NP 难。构造证明本身没有问题:要证存在,给出一个构造就是证明。要分清哪一段是借的:规约链借的是 Cook–Levin,空间、迭代列、P 居民是我们搭的。看到「构造 3-SAT」,不要以为构造这个动作自动产生了 NP 难——难跟着老链子来,不跟着新构造来。这条构造证明,证的是空间里有谁、没有谁。

P 居民取 L=2 一侧构造;L=3 一侧的 NP 难对象由 Cook 规约链拴定。

2-SAT 情形取 L=2:D={0,1}2={00,01,10,11},4 个状态。把 L=2 的值带进来:A2 有 4 个状态加 3 个算子,共 7 个值;空间 X2=A2D 有 74 个点。居民只用到状态那 4 个值——记 B:={0,1}2⊂A2,0:=(0,0),1:=(1,1),∧ 在 B 上逐比特作用;整条轨道落在 BD⊂X2 里,共 44=256 个点。汉明距离是整数,落在 0,1,…,4 之间。

从头推。先定乘子:

h:D→B,h(x1,x2):=(x1,x1)

只读第一个比特,把它写进两个槽位。四个输入的取值逐个列出:

x00011011
h(x)00001111

读一位、写两位,代价 O(1),属于 P 一侧;且 h∈BD⊂X2。

再把算子定成逐点合取:

Th(f)(x):=f(x)∧h(x)(x∈D)

起点取常一函数:

a0:=1X,a0(x)=11(x∈D)

第一步逐点算,四个输入各做一次两位合取:

a1(00)=11∧h(00)=11∧00=00a1(01)=11∧h(01)=11∧00=00a1(10)=11∧h(10)=11∧11=11a1(11)=11∧h(11)=11∧11=11

四个值挨个看下来,11∧v 的两位都是 1,合取原样放过每一位(1∧0=0,1∧1=1),结果就是 h 在这一点的值。故

a1=h

第二步再逐点算:

a2(00)=a1(00)∧h(00)=00∧00=00a2(01)=a1(01)∧h(01)=00∧00=00a2(10)=a1(10)∧h(10)=11∧11=11a2(11)=a1(11)∧h(11)=11∧11=11

h 的两个槽位相等,每个输入上合取的都是两个相同的两位值,逐比特 0∧0=0、1∧1=1,结果还是它自己:h∧h=h。于是 a2=a1,往后每一步都一样:

an=h(n≥1)

距离账也逐个坐标点清:

d(a0,a1)=|{x∈D: 11≠h(x)}|=|{00,01}|=2d(a1,a2)=|{x∈D: h(x)≠h(x)}|=0

即 δ0=2,δ1=0。δn 是 0 到 4 之间的整数,从 δ0=2 出发一路不增(0≤q<1⇒qnδn≤δn),第 1 步就落到 0,此后恒为 0。迭代条件 Δn≤qnδn:n=0 时 0≤2;n≥1 时 0≤0,处处成立。

因此

aP∗:=h∈X2

P 居民构造完成:一步后冻结,极限是空间里的显式点 h。

这个居民特殊,特殊在两处。它的极限是 X2 里的点 h,不是 −∞:一步之后每一位都定死,再推只是重复。它又恰好让 2 个状态满足——h(x)=11 只在 10、11 上成立,其它两个输入给出 00。3-时间门要数到第三个满足状态才开;L=2 的全部行为里凑不出第三个,门永远关着。P 居民就住在这扇关着的门里面。

5.3 NP 反例 ​

反设存在 NP 居民 aNP∗,其不动点为 −∞。由 §3.3、§4:

aNP∗=−∞∉X

NP 侧的迭代列 {an} 满足 §2.1 的条件,在 N≤9 步内冻结:

aN=aN+1=⋯=a∗∈X

故 liman=a∗∈X,这与 liman=aNP∗=−∞∉X 矛盾。

所以 NP 居民不存在;反例对象就是 −∞ 本身,它不在空间里。

5.4 结论 ​

P-resident:aP∗=h∈X2(L=2,5.2 显式构造)NP-resident:aNP∗=−∞∉X(L=3,5.3 反证不存在)⇒ P≠NP

6. 回到理想时间 ​

6.1 神谕时间已经在手上 ​

人们说理想时间下的 NP 难问题,好像理想时间是一样额外的、够不着的东西。这本书里的理想时间不是额外的。它就是 §1.3.3 的神谕时间,也是 §2 那条迭代列的时间 n。序列在哪里停,理想时间就到哪里。

它已经被证出来了。迭代条件里的 qn,从第一步以后不再变大:n≥1 时 qn≤q。把这个统一的衰减常数记作

Q:=q

于是每往后推一步,相邻两项的距离至多乘上 Q:

δn+1≤Qδn(n≥1)

连乘到第 n 步:

δn≤δ1Qn−1(n≥1)

δ1 是第一步之后的相邻距离,不超过坐标总数 |D|。所以

δn≤|D|Qn−1

这条不等式就是理想时间账。Q 是衰减常数,|D| 是空间的大小;一个来自迭代条件,一个来自空间。变个形就能算。

6.2 剩余多少,时间多少 ​

设还剩 ε 没有走完,即要求 δn<ε。由上式,只要

|D|Qn−1<ε

两边取以 1/Q 为底的对数(1/Q>1,不等号方向不变):

n−1>log1/Q⁡|D|ε

即

n>1+log1/Q⁡|D|ε

右边只用到三个数:空间大小 |D|、容差 ε、衰减常数 Q。空间大小写在空间里,容差是要求,衰减常数写在迭代条件里,没有一个是外来的。这就是剩余距离 ε 所对应的神谕时间上界。ε≥|D| 时不用再走;Q=0 时一步冻结。

这条上界就是证书:不用写起点差 δ0,写一个 Q 就够了。Q 是这条列的衰减常数,δ0 只是这一趟从哪里出发。

6.3 理想状态的时间上界 ​

理想状态是 δ=0。空间里的距离取有限个值,取 δmin 为其中最小的正距离(§5.1):δn<δmin 只能推出 δn=0。把 ε=δmin 代入:

nideal∗≤⌈1+log1/Q⁡|D|δmin⌉

把 L=3 的数带进去:|D|=8,δmin=1,于是

nideal∗≤⌈1+log1/Q⁡8⌉=⌈1+ln⁡8ln⁡(1/Q)⌉

Q 是衰减常数,固定不动;右边因此是一个常数。理想时间是有限的,也数得出来。

这和 §3 接得上。对数空间里的那条不等式,只在 δn>0、序列还在动的时候有内容(§2.2);序列一停,它就到头了。理想时间就是这段不等式的长度。把理想时间说成够不着的东西,是把它当成了极限;在这里它是一串数得完的台阶。

6.4 两条神谕时间 ​

P 居民这边,证书当场就开得出来。第一步之后 δ1=0,衰减常数取 Q=0:距离已经压到零,再推只是重复。理想时间 1,一步到底。乘子是闭式的 h,只读第一位;候选表 X2 有 74 个点,它只碰 a0 与 h 两个。神谕时间是 1;候选表再大,它也只走一步。

NP 一侧开不出证书。证书要有一个空间里的停点,Q 才有地方落笔;−∞ 不在空间里,笔落不下去。硬要给它记一笔神谕时间,只剩穷举:把整叠候选表摊开,L=3 时 X3 有 118≈2.1×108 个点。L 每加 1,AL 从 7 个值长到 11 个、再到 19 个,XL 从 74 长到 118、再到 1916——底数和指数一起长,指数叠指数。这笔账的上界是爆炸性的指数几何。

两条线不一样。P 居民的证书上写着一个 Q(这里是 0),理想时间是 1,多项式线性的;NP 居民连证书都开不出来,只剩候选表的整叠大小,爆炸性的指数几何。P≠NP 放在时间轴上,就是这两条线永远不碰。


书在这里结束。

它是一本开放的书。证完的摆在这里,没证完的也摆在这里。第24章的结论停在 P≠NP,后面没有下一页了。

走向明天不需要先成为一个能被写下来、完整、正常、勇敢、没有恐惧和羞耻的人。谁也没有这个义务。

明天不会给我们开正门。那就穿涉过去。照样感受世界,照样想象,照样生活。

穿涉了,就是过了。

祝你好运。