第24章:NP 问题的探讨——LIT 定理
路线:定义空间与距离
前言:先穷举,再说收敛
一个子句,三个变量。字面量怎么排、插什么值、插什么算子、加什么条件,读到最后都是同一件事:这组取值下,子句满不满足。除此之外,它没有别的行为。
所以不去猜它的结构,只列它的行为。三个变量各取
八个答案不分开跑。把它们叠在一起,收进同一条变量
这一步之后,收敛性是一个可以算的问题。
这办法不神秘,甚至很蠢:不懂子句的结构,就把取值全试一遍。可讲朴素不动点,就得用这个蠢办法。聪明一点的方法一上来就假定了结构,朴素性就没地方站。蠢办法把整个空间填满;填满了,不动点落在哪一格,才谈得下去。
1. 空间
1.1 值集合 (平凡基础)
对每个
到空间上就是常一值函数
1.2 构造 与完备空间
取
| 编号 | 状态 |
|---|---|
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 |
3-SAT 情形取
1.3 构造 与完备空间
取
| 编号 | 状态 |
|---|---|
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 |
2-SAT 情形取
1.3.1 不是 3 位/2 位填表,而是整个解空间沿时间轴迭代
枚举 8 个候选输入状态; 是整个候选解空间。 - 迭代对象
不是单个 3 位赋值,而是整张候选表:8 个状态的值同时被包在 里,沿时间刻度 一起演化。 - 时间门只数「恰好 3 个满足状态」:
时,整个空间才允许推进到 ;否则时间停住,无法往外推。
所以「3」是当前时间片上恰好满足的 3 个状态,不是输入长度;「2」同理,最多只有 2 个满足状态,变不出第 3 个,3-时间门永远关闭。
1.3.2 最优时间:只计成功推进
回溯、改错、踌躇不前的分支不进时间账。只记录真正过门、成功向前的步骤:
1.3.3 离散时间与神级机器(绝对最优时间)
时间取离散刻度
Oracle 时间(神谕时间)是一个名词:它指没有任何改错、完全贴着状态空间成功路径演化的最理想时间。它不是新增的物理机器,也不是额外的计算能力;它只是给这个最理想时间起的名字。设想一个神谕(oracle)作为这个理想演化者:每一步都完全贴着状态空间里成功的那条路径走,失败、回溯、改错的分支根本不进入时间账。它的时间定义成
这个
- 上界:确实存在一条
步成功路径(神谕到了); - 下界:任何成功路径都不短于
; - 回溯、改错、踌躇不前的时间全部归约掉,不计入
。
它是神谕的时间,不是任何物理机器的实际时间;物理机器只能比它慢。
1.4 加权汉明距离
空间是离散的:
几何性质:
- 取值为整数
; - 相邻即「恰好一个坐标不同」,
是有限积图上的最短路径长度; - 单位权时,以
为心、半径 的球是「至多 个坐标不同」的函数集,是子立方体的并。
加权汉明在每个坐标上乘权重
- 度量的汉明型由离散性决定,权重不改变这个型
普通汉明距离 - 一般值集合:
, 为 上的离散度量
3-SAT 情形(
范数形式(
1.5 完备性
是值集合, 是值函数空间, 、 、 逐点作用。 - 逐点结构
完备性按坐标继承: 是每个输入坐标上一份 的积。 是半环 / 格 / 有补 是; 完备 完备。 - 度量侧:加权汉明是逐坐标聚合。输入集有限
有限 柯西完备自动成立;无限时, 的完备性由 的距离完备性决定。 - 表达侧:
逐点生成 上的函数代数;能生成全部值函数,靠的是 本身是布尔值集。
一句话:这个值函数空间的完备性是继承来的——
2. 迭代列
2.1 最朴素的单变量迭代
迭代对象不是单个值,也不是单个变量
- 所有值集合
- 所有状态
- 所有变量的全部取值方式
全部包进
在完备空间
迭代条件:
证明它确实是柯西列。这条证明只用一个事实:距离是整数,而且只有有限多个可能的取值。
记
因为
相邻两项的距离一路不增。
先看第一格。
再紧一格。
取
序列不再动,是常列。常列是柯西列,极限就是这个点;所有
拿 11 验一遍:
加权汉明是同一本账,只是每一格的价钱不同:
2.2 迭代条件的除法形式
记
把迭代条件右边的乘子除到左边:
- 左边:像的距离
除以原像的距离 - 右边:指数函数形式
为什么要把乘子除到左边?
除法也把假设写在了分母上:只有当
3. 对数空间
3.1 换底公式
换底公式:
把真数替换为分子
除法不等式换到对数空间:
- 指数形式
在对数空间变成线性项 - 除法式与换底公式同构:分子
真数,分母 底数
换底公式本身就是一次除法。分子是真数,分母是底数;§2.2 的比值和对数刻度上的商是同一件事,写成减法就是
连乘变连加只靠一条性质:
缩放换成了平移。而
3.2 真分数
即
3.2.1 为什么这一项会走到
右边的
左边被
左边本来有别的去处。
所以左边的全部可能值是一个有限集,再加上
3.3 取极限
令
上界跑到
- 极限在
- 不动点也在
4. 矛盾
但这个空间是离散空间,没有
一边不动点在
5. P 居民与 NP 反例
以下结论都在 §1 的离散空间
5.1 离散性引理
设
即柯西列的极限是
5.2 与 P 居民
:2-SAT, ; :3-SAT, 完全(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 居民取
2-SAT 情形取
从头推。先定乘子:
只读第一个比特,把它写进两个槽位。四个输入的取值逐个列出:
读一位、写两位,代价
再把算子定成逐点合取:
起点取常一函数:
第一步逐点算,四个输入各做一次两位合取:
四个值挨个看下来,
第二步再逐点算:
距离账也逐个坐标点清:
即
因此
P 居民构造完成:一步后冻结,极限是空间里的显式点
这个居民特殊,特殊在两处。它的极限是
5.3 NP 反例
反设存在 NP 居民
NP 侧的迭代列
故
所以 NP 居民不存在;反例对象就是
5.4 结论
6. 回到理想时间
6.1 神谕时间已经在手上
人们说理想时间下的 NP 难问题,好像理想时间是一样额外的、够不着的东西。这本书里的理想时间不是额外的。它就是 §1.3.3 的神谕时间,也是 §2 那条迭代列的时间
它已经被证出来了。迭代条件里的
于是每往后推一步,相邻两项的距离至多乘上
连乘到第
这条不等式就是理想时间账。
6.2 剩余多少,时间多少
设还剩
两边取以
即
右边只用到三个数:空间大小
这条上界就是证书:不用写起点差
6.3 理想状态的时间上界
理想状态是
把
这和 §3 接得上。对数空间里的那条不等式,只在
6.4 两条神谕时间
P 居民这边,证书当场就开得出来。第一步之后
NP 一侧开不出证书。证书要有一个空间里的停点,
两条线不一样。P 居民的证书上写着一个
书在这里结束。
它是一本开放的书。证完的摆在这里,没证完的也摆在这里。第24章的结论停在
走向明天不需要先成为一个能被写下来、完整、正常、勇敢、没有恐惧和羞耻的人。谁也没有这个义务。
明天不会给我们开正门。那就穿涉过去。照样感受世界,照样想象,照样生活。
穿涉了,就是过了。
祝你好运。
