Valiant–Vazirani 1986：唯一可满足性怎样被随机归约钉成和 SAT 一样硬

破除误解：隔离不是「SAT 已经唯一」，随机归约也不是确定性算法#

第一层误解把标题听成「可满足实例本来就只有一个解」，或听成论文发现了 SAT 的唯一见证。 原文问的恰好相反。 已知的 NP 完全问题里，有解实例的解数可以从一跳到指数多个。 大多数与 SAT 个数保持互归约的问题都是这样。 困难会不会就是被这份宽变化养活的？ 九页给出的是否定答案：把变化强行压到「零或一」，随机归约下硬度仍在。 隔离是事后加上的随机约束，不是对原实例解数的观察。 把「检测唯一解」听成「公式已经唯一」，会把一次加压手续收成一次统计学事实。

第二层误解把随机多项式归约听成已经给出一台确定性多项式算法，或听成已经证明 $NP=RP$。 期刊里的归约是带硬币的。 否实例上，输出永远落在「无解」一侧。 是实例上，输出以至少多项式分之一的概率落在「恰好一解」一侧。 成功概率不必接近一，只要与输入规模的倒数同阶。 独立重复仍停在随机多项式时间里。 若「零对一」本身已经属于 $RP$，硬币才会把 SAT 一并吞进去，那才得到 $NP=RP$。 原文给的是条件句。 把归约听成算法，会把一次存在性翻译收成一次求解器。 本页没有、也不声称已经裁决 $P$ 对 $NP$，或 $NP$ 对 $RP$。

第三层误解把 Unique SAT 听成 计数复杂度 总览，或听成「数完所有解」。 「检测唯一解」是承诺问题：输入被答应只有零个或一个满足赋值，机器只需说出是哪一边，多于一个解时的输出可以任意，但必须停机。 Unique SAT 作为语言则问「是不是恰好一个」，两个以上与零个都要答否。 后者落在帕帕季米特里乌与扬纳卡基斯 1984 年的差类 $\mathrm{D}^{\mathrm{p}}$ 里：它是一个 NP 语言与一个 coNP 语言的交。 前者是标题里的「detecting unique solutions」。 两句话共用「唯一」，窗口不同。 计数总览要的是整个整数。 本页要的是零对一这扇最窄的窗。 把三页焊在一起，会把一次承诺硬度收成一次计数地图。

第四层误解把 1985 年 STOC 与 1986 年 TCS 焊成一次印刷，或把隔离听成 1987 年那条给最小权孤立唯一解的引理。 会议六页与期刊九页是先印与展开。 文件名取 1986，是课堂标准名称钉在期刊上。 随机权隔离是后一年的邻居，对象是带权极小解，不是本页的二维线性约束。 把两份会议录、一条后年引理收成一句「隔离引理」，会把一次随机归约收成一次权值抽样。

第五层误解把本页读成户田定理、读成概率可验证明，或读成哈斯塔德那种间隙不可近似。 户田要用隔离，但不能把 1991 年的层次包含提前写进这九页。 后两条战线都不在页码 85 至 93 里。

随机超平面、零对一，以及差类上的随机完全性#

装置从承诺问题开始，而不是从「再数一遍」。 设 $A$ 是任一与 SAT 个数保持互归约的 NP 完全问题。 对任意谓词 $Q$，期刊定义一种放松：零解时答案必须为否，一解时必须为是，多于一解时交给 $Q$ 任意作答。 主定理说：存在从 SAT 到这种放松的随机多项式归约，且对每个 $Q$ 都成立。 于是，零对一这扇窗已经够硬。 找唯一解的承诺版——答应恰好一个见证、允许在其余实例上胡说——同样在随机归约下对 NP 困难。 本页证明这种翻译手续存在。 它不把约束清单写成解题步骤。

约束的几何被写在二元域上。 满足赋值看成 $\mathrm{GF}(2)^n$ 里的向量。 随机取若干向量，用内积为零截出超平面，相当于对未知解集做一次粗糙的对半切割。 切割不必独立到每个解，也不需要指数多的硬币。 卡特与韦格曼 1979 年那种普遍哈希的存在性，加上西普塞尔、斯托克迈耶此前把内积用在随机性与近似计数上的观察，足够保证：若原公式可满足，则沿一串随机超平面走下去，以至少四分之一的概率会在某一步恰好剩下一个解。 再在多项式多个深度里随机停一步，成功概率仍与 $n$ 的倒数同阶。 若原公式不可满足，截完仍然为零。 零永远是零。 一以不可忽略的概率出现。 「有没有解」于是以单侧错误变成「零个还是一个」。 隔离失败时解可能仍有许多。 有界错误允许这件事以小概率发生，那不是把哈希表交给求解器之前的预处理。

奇偶从同一扇窗读出。 零对一的差，模二看得见。 于是，计算 SAT 满足赋值个数的奇偶，在随机归约下对 NP 困难。 对任一大于一的模 $k$，个数是否被 $k$ 整除，同样困难。 瓦利安特 1979 年把公式译成 0-1 矩阵、使积和式等于解数乘上已知的 $4$ 的幂。 本页接上这一步：当模数不是 $2$ 的幂时，0-1 积和式模 $k$ 也在随机归约下对 NP 困难。 判定「有没有完美匹配」仍在 $P$ 里。 模掉之后的只读奇偶，却把随机钉子钉回去。 这是 1979 年完全性的一条随机推论，不是把那十三页再印一遍。 本页不把矩阵填写写成求值手册。

Unique SAT 作为语言走另一条走廊。 塞尔曼指出，它可以承接差类上的随机完全性。 帕帕季米特里乌与扬纳卡基斯把 $\mathrm{D}^{\mathrm{p}}$ 写成两个 NP 语言的差，并证明 SAT-UNSAT——一对公式里前者可满足、后者不可满足——对这个类完全。 期刊把随机隔离接到前一个公式上，再给后一个公式补上恰好一个额外解，于是一对公式并成「是不是恰好一个」。 推论 3.5：Unique SAT 在随机多项式归约下对 $\mathrm{D}^{\mathrm{p}}$ 完全。 布拉斯与古列维奇 1982 年那篇《On the Unique Satisfiability Problem》已经把 Unique SAT 放进差类，并证明：在会相对化的确定性归约下，它不能对 $\mathrm{D}^{\mathrm{p}}$ 完全。 他们构造了两座神谕，一座让它不完全，一座让它完全但 $NP\neq coNP$。 确定性钉子被相对化挡住。 随机钉子从旁边绕过去。 把 1986 年听成「Unique SAT 早已在确定性多一归约下完全」，会把一次随机完全性收成一次被神谕禁止的确定性完全性。 屏障属于 1982 年。 绕开属于 1986 年。

密码学读法写在摘要末句。 核心问题是：有没有 NP 问题，其实例的解唯一、却仍然难找。 九页并不把这样一个问题放进无歧义类 $\mathrm{UP}$。 每个 $\mathrm{UP}$ 语言确实可以确定性归约到上述放松，但放松本身不知是否属于 $\mathrm{UP}$，因此证明没有给出 $\mathrm{UP}$ 里的困难成员。 它给出的是一种更弱、也更刺耳的信念：唯一性并不能把 NP 硬度卸掉。 随机手续可以在不知解在哪里的情况下，把多解压成稀解。 「唯一但难」不必等待大自然碰巧只留下一个见证。 这是存在性解释，不是一份把哈希约束焊进公钥方案的装配说明，更不是攻击步骤。 概念证据到此为止。

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

它证明了：存在从 SAT 到「零解对一解」承诺问题的随机多项式归约，且对任意在多解上的放松都成立。 因此，分辨零个与一个满足赋值，与找出被答应唯一的那个赋值，都在随机归约下与 SAT 一样硬。 若这种承诺问题属于 $RP$，则 $NP=RP$。 它还证明：SAT 解数的奇偶、以及解数模任意大于一的整数，都在随机归约下对 NP 困难。 当模数不是 $2$ 的幂时，0-1 积和式的相应模运算同样困难。 Unique SAT 作为语言，在随机多项式归约下对 $\mathrm{D}^{\mathrm{p}}$ 完全。 用后来课堂的话说，这就是「隔离」：随机约束把存在性压成稀解，硬度几乎不掉。

它没有证明 $P\neq NP$，也没有证明 $NP=RP$。 随机归约里的硬币不会自己变成确定性手续。 它没有给出从 SAT 到 Unique SAT 的确定性归约。 开放问题写在第四节：任何会相对化的确定性归约，都被 1982 年的神谕挡住。 它没有把困难问题放进 $\mathrm{UP}$，因此没有造出「唯一见证且属无歧义 NP」的完全问题。 它没有覆盖积和式的 $\#\mathrm{P}$ 完全性，那是 1979 年的对象。 它没有覆盖多项式层次被一次计数询问吞掉，那是 1991 年的对象。 杰勒姆–瓦利安特–瓦齐拉尼的抽样与近似计数等价、非负积和式的 FPRAS、算术电路里 VP 对 VNP，都不在这九页里。 概率可验证明与哈斯塔德式不可近似性同样不在。 对照属于总览页。 它也没有打开电路下界，没有构造使 $NP$ 与 $RP$ 相对化后分开或重合的神谕——1982 年的神谕管的是差类上的确定性完全性，不是这一对随机类。 稳健性来自随机超平面把未知解集切稀。 本页把「这种切割在数学上存在、且成功概率与规模倒数同阶」写成结构事实。 两句都不是操作单。

跨域连接#

• 计数复杂度：总览页把 $\#\mathrm{P}$、户田定理、FPRAS 与 Holant 收成一张学科地图。
• 本页只提供地图上「零对一已经够硬」的那枚随机钉子。
• 钉子的金属成分以 1986 年的承诺问题、奇偶与差类为准，不是后来的近似抽样，也不是签名二分。
• 把两页叠在一起读，才能看见：计数类先作为「数接受计算」出现，隔离再把存在量词改写成奇偶能读的窗口。
• 地图可以后写。
• 随机归约的方向以期刊定理 1.1 为准。
• 瓦利安特一九七九年积和式论文：那十三页把 0-1 积和式写成 $\#\mathrm{P}$ 完全，并指出判定容易并不蕴含计数容易。
• 本页借用其中「公式到矩阵、积和式带着 $4$ 的幂」的编译，把随机钉子钉到「模一个不是 $2$ 的幂的整数」。
• 没有 1979 年的函数，1986 年的模推论没有对象可乘。
• 没有 1986 年的随机归约，1979 年的完全性只压在计数函数上，压不到「零对一」这扇判定窗。
• 把积和式听成本页的证明，会把一枚完全钉子收成一次隔离。
• 户田一九九一年论文：那十三页把本页的隔离当成第一级台阶，再把奇偶拉成多数看得见的缺口，最后让一次 $\#\mathrm{P}$ 询问吞掉多项式层次。
• 本页停在台阶上：存在量词随机变成稀解。
• 户田继续往上走，交替量词才被收进同一扇窗口。
• 把 1986 年听成层次已经被计数神谕罩住，会把一枚随机钉子收成一次无条件包含。
• 两页必须分开写，才能看见隔离是构件，不是户田定理本身。
• 库克一九七一年论文：那八页把「存在接受计算」编译成可满足公式。
• 本页从同一份存在性出发，却要求随机约束把「有没有」变成「零个还是一个」。
• 库克问有没有。
• 本页问：若只答应处理唯一见证，难度会不会掉下来。
• 答案是：在随机归约下不会。
• 个数保持的编译在这里是前提，因为隔离必须作用在解集合上，而不是作用在另一个被扭曲过的计数对象上。
• 把 1986 年听成 SAT 判定，会把随机钉子收成 1971 年的存在性钉子。
• 随机算法：算法页管蒙特卡洛、拉斯维加斯与误差放大在素数检测上的形状。
• 本页把同一枚硬币从「算法内部的错误率」改写成「类与类之间的归约语言」。
• 单侧错误、多项式分之一的成功概率、独立重复仍停在 $RP$ 里——这些是复杂度闭合性，不是把米勒–拉宾的轮数表写成实现步骤。
• 把随机归约听成已经给出 SAT 的蒙特卡洛求解器，会把一次存在性翻译收成一次产品算法。
• 密码学基础：公钥故事需要「解唯一却仍然难找」这种对象。
• 摘要把本页读成对这种信念的加强：随机隔离说明，多解并不是 NP 硬度的来源，压成唯一之后硬度还在。
• 它没有造出 $\mathrm{UP}$ 完全问题，也没有给出单向置换。
• 格罗尔曼与塞尔曼 1984 年在 FOCS 上追问安全公钥与无歧义计算的关系，是邻居，不是把这九页再印一遍。
• 本页不把隔离约束、哈希族或唯一见证写成拆解步骤，更不提供如何利用稀解去攻一个系统。
• 计算复杂性：总览把 $P$、$NP$ 与随机类画成判定地图。
• 本页给出地图上 $RP$ 这一格为什么会碰到 Unique SAT：不是因为唯一性更细，而是因为随机归约允许在不知解在哪里时把解集切稀。
• 若零对一可被随机多项式手续诚实切开，整座 $NP$ 会掉进 $RP$。
• 把隔离听成「又证明了 $P\neq NP$」，会把一次条件句收成一次分离。
• 库克回答存在性完全。
• 瓦利安特 1979 年回答计数完全。
• 本页回答唯一性不能卸掉存在性硬度。
• 证明：这九页证明的是一份翻译手续存在：SAT 的句子可被随机改写成对零对一窗口的一次询问。
• 证书是归约，不是一张已算出的满足赋值表。
• 数学里的普遍证明要求从公理推出必然。
• 这里的必然相对于有界错误的硬币：否实例上从不说错，是实例上以多项式分之一的概率说对。
• 隔离是证明策略，不是把公式交给求解器之前的预处理。
• 把包含听成已经给出 Unique SAT 的确定性算法，会把翻译手续说成求值手续。
• 概率论：随机超平面把未知有限集切稀，靠的是二元域上内积的对称，不是对满足赋值做统计抽样。
• 成功概率不必接近一，只要与规模倒数同阶，再被独立重复放大。
• 期望与方差的精确式在期刊里由杰勒姆指出，拉宾的秩归纳把下界收到四分之一。
• 概率在这里是归约语言，不是把判定改成平均情形。
• 把存在性听成「随机抽一次赋值就能隔离」，会把一次计数收成一次实验。

参考文献#

• L. G. Valiant & V. V. Vazirani, "NP is as easy as detecting unique solutions", Theoretical Computer Science 47, 1986, pp. 85–93. DOI: 10.1016/0304-3975(86)90135-0. —— 本文对象：SAT 随机归约到零对一承诺、奇偶与 Unique SAT 的随机 $\mathrm{D}^{\mathrm{p}}$ 完全性。
• L. G. Valiant & V. V. Vazirani, "NP is as easy as detecting unique solutions", Proceedings of the 17th Annual ACM Symposium on Theory of Computing, Providence, Rhode Island, 6–8 May 1985, pp. 458–463. DOI: 10.1145/22145.22196. —— 会议先行本，用以标明与 1986 年期刊不是同一印刷。
• L. G. Valiant, "The Complexity of Computing the Permanent", Theoretical Computer Science 8(2), 1979, pp. 189–201. DOI: 10.1016/0304-3975(79)90044-6. —— $\#\mathrm{P}$ 与积和式完全性，用以标明本页钉的不是那枚完全钉子。
• Seinosuke Toda, "PP is as Hard as the Polynomial-Time Hierarchy", SIAM Journal on Computing 20(5), 1991, pp. 865–877. DOI: 10.1137/0220053. —— 后年邻居：隔离被用作把层次送进一次计数询问的台阶，不是本页封面。
• Andreas Blass & Yuri Gurevich, "On the Unique Satisfiability Problem", Information and Control 55, 1982, pp. 80–88. DOI: 10.1016/S0019-9958(82)90439-9. —— Unique SAT 进入差类，以及会相对化的确定性归约不能给出 $\mathrm{D}^{\mathrm{p}}$ 完全性。
• C. H. Papadimitriou & M. Yannakakis, "The Complexity of Facets (and Some Facets of Complexity)", Journal of Computer and System Sciences 28, 1984, pp. 244–259. DOI: 10.1016/0022-0000(84)90068-0. —— $\mathrm{D}^{\mathrm{p}}$ 与 SAT-UNSAT 完全性，Unique SAT 的随机完全性从这里接出去。
• Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971, pp. 151–158. DOI: 10.1145/800157.805047. —— 存在性编译，隔离从这里把「有没有」改写成「零个还是一个」。
• J. L. Carter & M. N. Wegman, "Universal Classes of Hash Functions", Journal of Computer and System Sciences 18(2), 1979, pp. 143–154. DOI: 10.1016/0022-0000(79)90044-8. —— 普遍哈希的存在性，期刊把二元域内积读成这一类对象。

延伸阅读#

• 与 计数复杂度 对读：先看 1986 年的零对一，再看总览怎样把隔离接到户田与奇偶。
• 与 户田一九九一年论文 对读：隔离是台阶，层次包含是后年的钉子。
• 与 密码学基础 对读：唯一但难是信念，不是一份已造好的 $\mathrm{UP}$ 完全问题。