Ladner 1975：若 P 不等于 NP，中间问题怎样必须存在

破除误解：中间问题不是「还没分类的自然题」，也不是已经分开 P 与 NP#

第一层误解把标题听成「拉德纳找出了一道既不难也不容易的自然问题」，或听成图同构、整数分解已经在 1975 年被写成中间档。原文构造的语言来自完全问题的长度切片：某些长度上抄写 SAT，某些长度上留下空段，切换由一只多项式时间可计算的钟决定。语言在 $NP$ 里，因为它的成员资格是「属于 SAT」再合上一个关于长度的多项式谓词。它没有图论或数论的日常名字。图同构、分解后来成为自然候选，那是后话，不是这十七页的对象。把拉德纳听成已经给图同构颁发中间证书，会把一条存在性对角化收成一份问题名录。

第二层误解把条件句听成分离。定理说的是：若 $P\neq NP$，则中间语言存在。它没有证明 SAT 不属于 $P$，也没有证明中间语言在现实世界里真的坐在那里。若 $P=NP$，完全档与 $P$ 重合，中间的座位被撤掉，同一套填充手续仍会写出一个 $NP$ 语言，只是它会掉进 $P$。把 1975 年读成「已经证明 $P\neq NP$」，会把一张关于度数结构的条件句收成一份悬赏答卷。完全性给出的同样是条件句：若 SAT 进入 $P$，则整个 $NP$ 进入 $P$。拉德纳补上的是另一侧：若 SAT 不进入 $P$，则 $NP$ 不能只分成「容易」与「完全」两格。

第三层误解把本页听成贝克、吉尔与索洛维的神谕世界，或听成「对角化已经失效，所以中间问题无法讨论」。贝克–吉尔–索洛维一九七五年论文 构造了两个神谕：一个让 $P^A=NP^A$，一个让 $P^B\neq NP^B$。相对化因此不能单独裁定未加神谕的问题。拉德纳的手续在有神谕的世界里同样能跑：只要 $P^A\neq NP^A$，相对化的中间度数就存在；只要两边重合，中间度数就空。两篇同属 1975 年，回答的不是同一句话。障碍的清单见 P vs NP 的证明障碍。本页不把神谕装配写成操作单。

第四层误解把「稠密」听成经验统计，或听成卡普名单上必定漏了一题。稠密说的是偏序：若递归语言 $A$ 严格多项式归约到递归语言 $B$，则中间还插得进另一个递归语言 $C$。$NP$ 中间性是特例——下端取 $P$ 里的语言，上端取 SAT，并假定 SAT 不在 $P$ 里。卡普的二十一题全部停在完全档；名单再长，也不回答完全档与 $P$ 之间有没有座位。把稠密听成「大多数组合问题都是中间的」，会把一条关于度数的数学命题收成实验室口碑。

延迟对角化、填充，以及多项式归约的稠密序#

装置从两种箭头开始。多项式时间图灵归约允许询问机在多项式步内向神谕提问，也就是 库克一九七一年论文 的口径。多项式时间多一归约只允许一次确定性映射，是与否保持同向，也就是 卡普一九七二年论文 的口径。两种关系都在递归语言上给出偏序；互相可归约的语言构成同一个多项式度数。$P$ 是最底下一档。$NP$ 完全是 $NP$ 里的最上档，前提是用多一把每个 $NP$ 语言都送到它那里。本页问的不是再钉一枚完全钉子，而是：这两档之间的序有多密，空位能不能被多项式时间可写的填充填上。

普通对角化在这里套不上现成的时钟。哈特马尼斯–斯特恩斯一九六五年论文 证明：给图灵机严格更多的可构造时间，就能识别严格更多的语言。模拟器在更长的预算里跑完对手，再翻转答案。中间语言必须停在 $NP$ 里，核对只能是多项式的，没有「再给一截指数时间」可花。同一输入上既要模拟多项式机器、又要保持自己的多项式时钟，预算不够。拉德纳把翻转推迟到更长的输入：在长度 $n$ 上，只用大约 $n$ 步回头看更短的串，检查当前这台多项式机器或当前这条归约是否已经被看穿。看穿了，就切换工作模式；没看穿，就沿用同一模式，把 SAT 的硬材料或空段的易材料继续铺下去。这就是延迟对角化，也叫回看。延迟不是把证明藏起来，而是把模拟费从当前串转移到已经写完的短串上。

填充是买时间的几何，不是给实例化妆。取一个 SAT 实例 $\varphi$，在后面接上一长串填充符号，长度仍是 $|\varphi|$ 的多项式。剥掉填充、补上填充，都可以在多项式步内完成，因而 SAT 与它的填充版本属于同一多一度数。硬材料可以被拉长，铺过许多长度，而不改变它在归约序里的位置。空段是反向的填充：这些长度上语言为空，多项式机器看起来像在判定一个有限集。钟本身必须是多项式时间可计算的，否则写出来的语言会掉出 $NP$。钟的读数决定当前长度抄写 SAT 还是留下空段。两种材料交替，是为了同时对付两类对手：一类对手声称自己是多项式时间判定器，一类对手声称自己是从 SAT 出发的多一归约。

两类要求轮流提出。若当前长度处于「抄写 SAT」的模式，语言在这些长度上与完全问题重合。一台真正的多项式判定器若在这些长度上一直正确，回头模拟就会看见它在给 SAT 当判定器；若 $P\neq NP$，这种正确性不能无限持续，于是判定器终将被看穿，钟转入另一模式。若当前长度处于「空段」模式，从 SAT 出发的多一归约会把某些实例送进空段。送进空段的实例必须是「否」实例，否则归约已经失败；若归约把足够多的「是」实例也送进空段，回头模拟就会看见归约失败。若归约始终把「是」实例送进仍在抄写 SAT 的长度，而空段无限延伸，则 SAT 自身会被多项式手续拆开。假定 $P\neq NP$，两种「永远不切换」都会导致矛盾。于是钟必须无限次改换读数，两种材料都无限出现。写出来的语言因此不能是有限的，不能被任何一台多项式机器判定，也不能充当 $NP$ 完全的汇点；它仍在 $NP$ 里，因为成员资格没有超出 SAT 加上长度上的多项式谓词。

稠密性把同一装置从「$P$ 与 SAT 之间」推到任意一对已经分开的递归度数上。设递归语言 $A$ 严格多项式归约到递归语言 $B$，也就是 $B$ 不能多项式归约回 $A$。把 $B$ 当作硬材料，$A$ 当作已经允许的底。填充与空段不再相对 SAT 与空集来写，而相对 $B$ 与 $A$ 来写。回看的对象改成：是否已经看见一台把中间语言归约到 $A$ 的多项式手续，以及是否已经看见一台把 $B$ 归约到中间语言的多项式手续。切换逻辑不变。于是严格不等式 $A<_p B$ 中间插得进 $C$，满足 $A<_p C<_p B$。多项式时间归约在递归语言上因此是稠密偏序，不是只有「底、顶、中间三格」的梯子。$NP$ 中间性是把底取在 $P$、把顶取在 SAT 时的推论，不是另一条定理。多一口径与图灵口径下都可以写下同类密度；完全性这一档在标准教材里按多一书写，本页的中间语言也按这一档来读。

这套手续回答的是「度数之间有没有位置」，不是「怎样把口令或协议写成中间语言去求解」。填充符号不提供窗口编码，也不提供求解器启发式。稀疏性在这里是长度切片的疏密，不是工业实例里约束的疏密。把填充听成「给难题补零就能变容易」，说反了方向：补零保持度数，挖空才改变度数，而挖空必须由那只回看的钟来调度。钟调度的是存在性证明里的材料，不是攻击步骤。

它证明了什么，没有覆盖什么#

它证明了：在 $P\neq NP$ 的假定下，$NP$ 不能只有 $P$ 与完全档两格，中间至少有一个语言，既可用非确定性多项式机器接受，又不能成为多一完全的汇点。它进一步证明：递归语言上的多项式时间度数是稠密的——任意两个已经分开的度数之间还插得进第三个。填充给出的是可计算的书写手续，不是事后追加的注释。用后来的说法，这就是「若 $P\neq NP$，则存在 $NP$ 中间语言」在 1975 年的原句。原句的主语是归约序的结构，SAT 只是把上端钉在完全档上的一枚钉子。

它没有证明 $P\neq NP$。条件句两边都不被对角化单独敲定。哈特马尼斯–斯特恩斯一九六五年论文 的层次是无条件的，因为它花得起更多时间；本页花不起，所以必须把「已经分开」写进前提。它也没有给出任何一道带日常名字的中间问题。构造所用的语言依赖枚举多项式机器与归约的那只钟，钟的设计可以改写，组合意义不会因此出现。图同构后来进入准多项式时间，分解落在 $NP\cap\mathrm{coNP}$ 里，两者都是候选故事，不是这十七页颁发的证书。

它没有覆盖相对化，也没有覆盖后来关于稀疏完全集的定理。贝克、吉尔与索洛维说明神谕世界里 $P$ 对 $NP$ 两种答案都有模型；本页说明未加神谕的世界里，一旦答案是「不等」，中间度数就必须密。两句叠在一起读，不能互相代替。马哈尼（Stephen R. Mahaney）1982 年证明：若存在稀疏的 $NP$ 完全集，则 $P=NP$。稀疏性与填充有亲缘，但那是另一枚钉子，不是 1975 年的密度定理。伯曼与哈特马尼斯 1977 年关于 $NP$ 完全集是否多项式同构的猜想，同样是后话。列文 1973 年的万能搜索谈证据翻译，不谈中间度数。

稳健性来自回看与填充可以相对于任意一对已分开的度数重写，不来自 SAT 这一种硬材料。只要上端语言不在下端的多项式闭包里，中间座位就可以用同一只钟排出来；多项式次数会变，稠密这一档不会变。概念证据到此为止。延迟对角化回答的是「多项式时钟下如何完成对角化」；填充回答的是「如何在不离开原度数或故意离开原度数之间做选择」。两句都不是操作单。

跨域连接#

• 哥德尔不完备定理：两边都靠自指把「关于系统的话」写回系统内部。哥德尔把「本语句不可证」编成算术公式；拉德纳把「当前这台多项式机器还没被看穿」编成长度上的钟。不完备性给出的是无条件的真而不可证；中间性给出的是有条件的存在。把拉德纳读成「$P$ 对 $NP$ 不可判定」，会把一条条件句收成一条元数学禁令。延迟也不是罗瑟式的「更短证明优先」：它优先的是已经结束的短输入，不是更短的形式证明。
• 可计算性：波斯特定出过递归可枚举集里的中间问题：是否存在既非递归、又非递归可枚举完全的集合。弗里德贝格与穆奇尼克在 1956 至 1957 年用有穷伤害优先方法给出肯定答案。拉德纳常被看成多项式时间里的对应物：把「递归」换成 $P$，把「递归可枚举完全」换成 $NP$ 完全。形状相似，引擎不同。优先方法在无限时间里修正无限次伤害；回看必须在多项式步内结束，只能把修正推迟到更长的输入。停机问题的多一完全性没有多项式时钟；这里的填充函数必须在多项式步内写完。把中间语言听成不可判定，会把资源问题收成存在问题。
• 数学哲学：存在性证明与自然例子在这里被拆开。拉德纳给出一台可以写下来的机器，它接受的语言在条件成立时坐在中间；这台机器并不对应图上的团、数上的因子，或任何先前出现在应用清单上的谓词。构造主义会追问「存在」是否必须伴随可展示的自然对象；这十七页给出的是可展示的手续，不是可展示的组合题。把手续听成已经找到「大自然写下的中间问题」，会把对角化的产物说成经验发现。柏拉图式的完全档与 $P$ 可以在理念里对峙，中间座位仍要靠填充才能被看见。
• 科学哲学：条件句在这里是可检验的结构命题，不是实验室口碑。证伪「若 $P\neq NP$ 则中间语言存在」，需要的不是又一道尚未分类的图论题，而是证明 $P\neq NP$ 同时 $NP$ 里每个语言要么在 $P$ 里、要么完全——这与密度定理直接冲突。科学内容是归约闭包与偏序密度，不是对单个谜题难度的直觉。把中间性听成「旅行商很难、2-SAT 很容易，所以中间还有一档」，说反了箭头：先有条件句下的存在，后有自然候选去填那个位置，而自然候选至今没有一张拉德纳式的证书。
• 集合论：稠密偏序是集合论里的老对象：有理数在实数里稠密，是因为任意两个不等的实数之间还插得进有理数。拉德纳把同一形状搬到多项式归约的度数上：任意两个已经分开的递归度数之间还插得进第三个。搬迁不是把语言等同于实数。实数的分隔靠中点；度数的分隔靠填充与空段的交替。没有那只回看的钟，中间点写不出来。把密度听成基数意义上的「中间语言有不可数多个」，会把偏序的插值收成集合的大小。

参考文献#

• Richard E. Ladner, "On the Structure of Polynomial Time Reducibility", Journal of the ACM 22(1), January 1975, pp. 155–171. DOI: 10.1145/321864.321877. —— 本文对象：多项式时间归约的度数结构、可计算填充与延迟对角化，以及 $P\neq NP$ 时 $NP$ 中间语言的存在。
• Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, Shaker Heights, Ohio, 1971, pp. 151–158. DOI: 10.1145/800157.805047. —— 询问机口径与 SAT 作为上端钉子所依据的编译。
• Richard M. Karp, "Reducibility among Combinatorial Problems", in Raymond E. Miller & James W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 85–103. DOI: 10.1007/978-1-4684-2001-2_9. —— 多一口径与完全档；用以标明二十一题停在上端，不回答中间座位。
• Juris Hartmanis & Richard E. Stearns, "On the Computational Complexity of Algorithms", Transactions of the American Mathematical Society 117, 1965, pp. 285–306. DOI: 10.2307/1994208. —— 带额外时间的普通对角化，用以对照本页在多项式时钟内必须延迟回看。
• Theodore Baker, John Gill & Robert Solovay, "Relativizations of the P =? NP Question", SIAM Journal on Computing 4(4), 1975, pp. 431–442. DOI: 10.1137/0204037. —— 相对化邻居：神谕世界里 $P$ 对 $NP$ 两种答案都有模型，不是本页封面。
• Richard M. Friedberg, "Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post's problem, 1944)", Proceedings of the National Academy of Sciences 43(2), 1957, pp. 236–238. DOI: 10.1073/pnas.43.2.236. —— 递归可枚举中间度数的优先方法解，用以标明可计算性类比的形状与引擎并不相同。

延伸阅读#

• 与 计算复杂性 对读：总览页把 $P$、$NP$ 与完全性收成地图；本页提供地图上 $P$ 与完全档之间那条缝的条件句。
• 与 库克一九七一年论文 对读：先看询问机与窗口编译如何钉上 SAT，再看本页如何把 SAT 切成硬段与空段。
• 与 卡普一九七二年论文 对读：二十一题停在完全档；本页问的是完全档之下还有没有座位。
• 与 贝克–吉尔–索洛维一九七五年论文 对读：相对化说明对角化搬不来分离；本页说明一旦分离成立，中间度数必须密。
• 与 户田 1991 对读：中间语言问的是 $P\neq NP$ 之下 NP 的度数缝；计数神谕问的是整座层次对一次 #P 查询有多软。两句都不是对单个谜题的直觉。
• 与 哈特马尼斯–斯特恩斯一九六五年论文 对读：普通层次花得起更多时间；延迟对角化花不起，只能回看。
• 与 P vs NP 的证明障碍 对读：条件句不是分离；相对化是障碍清单上的第一道，不是中间性本身。
• 与 可计算性 对读：波斯特问题与弗里德贝格–穆奇尼克给出递归可枚举中间度数；多项式时钟把优先方法收成回看。