结果族 235：Limiting random SAT thresholds, sharp variance and computability · 学科：Probability and statistical mechanics · 验证状态：暂无形式化证明，请以社区核验为准
阈值告诉你悬崖在哪里，方差告诉你悬崖有多宽。这篇论文证明：随机 3-SAT 里”崩溃时刻”（第一条压垮公式的子句出现的位置）的方差恰好正比于 n——悬崖宽度被精确钉在 √n 条子句，一步不多、一步不少。不同随机样本的崩溃点会散得多开？答案：标准差恰是 √n 的量级，再无悬念。
关键词卡片
看个具体例子
数字版定理：@@M@@\operatorname{Var}(H_n)=\Theta(n)@@。设 n = 10^6 个变量：崩溃时刻的典型偏差约 @@M@@\sqrt{n}=10^3@@ 条子句，只占总量的 0.1%；相应地，可满足概率从 99% 跌到 1% 也只需 @@M@@\Theta(\sqrt n)@@ 条子句——悬崖很陡，但不是刀刃。上界 @@M@@\operatorname{Var}(H_n)\le Cn@@ 是全新贡献，删去了姊妹篇 @@M@@O(n\log n)@@ 估计里的对数损失；下界则由 Wilson 定理直接推出。
为什么值得关心
与 k ≥ 4 的姊妹篇合成完整图景：一切 k ≥ 3 的方差都是 @@M@@\Theta(n)@@；而且全程不需要知道阈值在哪里，只围绕有限尺寸期望做文章。
暂无形式化证明（AI 结果待核验）
衔接《解读 Linear Variance of the Random 3-SAT Hitting Time》入门导读
第一级台阶
导读说”阈值告诉你悬崖在哪里，方差告诉你悬崖有多宽”。半数学地说：对象是逐条加入随机子句的增长过程中，第一条使公式无法被任何指派满足的子句的编号；要度量的量是这个”崩溃时刻”在不同随机样本间的散布程度——散布越宽，相变越温和。结论说散布的典型尺度恰被钉死：标准差与变量数的平方根同阶，不多不少。
第二级台阶
三个概念精确化。命中时间：上述首个不可满足时刻的下标，是一个取正整数值的随机变量。Efron–Stein 不等式：把总方差控制在”逐个删去一个随机输入（这里是一条子句）、观察输出推迟多少”的平方期望之和之下——于是证方差界化为逐条子句估计延迟。势函数：对指派集合 S，令 q_j(S) 为 j 条随机二元子句杀死 S（使其无成员幸存）的概率，对 j 求和得的量 P_d 有界、随 S 缩小而增，是给”解集还有多脆”定价的度量。
第三级台阶
定理的语境是三文字子句模型：每条子句均匀选三个互异变量、符号独立公平、整条有放回抽样。为什么单挑 k=3：族内姊妹篇的一般方法在此留下 n 与 n log n 之间的对数空隙——三文字子句恰好让”删除一条子句后每个可用根翻转都必须被该根的测试子句拦截”给出三个独立测试，而势函数的漂移估计恰能吸收立方概率，常数 3−3/2=3/2 的巧合使延迟平方可积。结论分两半：上界——存在绝对常数使方差不超过常数倍 n，这是全文新贡献，靠势函数去掉对数损失；下界——方差不小于常数倍 n，由 Wilson 2002 年的转移宽度定理短推导而得。两半合成：方差恰为 n 的常数倍尺度，相变窗口从概率 1−η 降到 η 需要且只需要 √n 量级的子句。值得注意的是全文不需要阈值位置的任何信息。
对 @@M@@n@@ 个变量上的随机 3-SAT，证明了首个不可满足前缀下标 @@M@@H_n@@ 的方差恰为 @@M@@\Theta(n)@@：新证明的上界 @@M@@\operatorname{Var}(H_n)\le Cn@@ 去掉了姊妹篇 @@M@@O(n\log n)@@ 估计中的对数损失，下界由 Wilson 转移宽度定理给出，从而确定随机 3-SAT 相变窗口的正确尺度是 @@M@@\sqrt n@@。
随机 @@M@@k@@-SAT 的相变研究不只问”阈值在哪里”，还问”窗口有多宽”。Friedgut 证明转移是尖锐的；Wilson（2002）证明 @@M@@k\ge3@@ 时可满足概率从一个固定水平降到另一个固定水平至少需要 @@M@@\Omega_k(\sqrt n)@@ 条子句，即窗口不能太窄；Carenini 的并发工作得到 @@M@@O_{k,\eta}(n^{1/2+1/k})@@ 的窗口上界与 @@M@@O_k(n^{1+2/k})@@ 的方差上界。窗口宽度由方差控制，但方差还取决于尾部，固定中心窗口的界并不足以给出方差界。同族姊妹篇对一般 @@M@@k@@ 证明 @@M@@\Theta_k(n)@@（@@M@@k\ge4@@），却在 @@M@@k=3@@ 留下 @@M@@n@@ 与 @@M@@n\log n@@ 之间的对数空隙；本文专攻三文字子句，把这个空隙闭合。
模型为独立、均匀符号、三变量互异、有放回抽样的 proper 3-clause 过程。定理：存在绝对常数 @@M@@C<\infty@@ 使 @@M@@\operatorname{Var}(H_n)\le Cn@@（@@M@@n\ge3@@）；另有绝对常数 @@M@@c>0@@ 与 @@M@@n_0@@ 使 @@M@@\operatorname{Var}(H_n)\ge cn@@（@@M@@n\ge n_0@@），故 @@M@@\operatorname{Var}(H_n)=\Theta(n)@@。推论：对每个固定 @@M@@0<\eta<1/2@@，可满足概率从 @@M@@1-\eta@@ 降到 @@M@@\eta@@ 的中心窗口宽度为 @@M@@\Theta_\eta(\sqrt n)@@。上界是全新贡献，下界由 Wilson 定理的短推导得到。值得注意的是全文不需要阈值位置的任何信息，只围绕有限尺寸期望 @@M@@\mathbb E H_n@@ 集中。
先把 @@M@@H_n@@ 截断在 @@M@@L=10n@@，记 @@M@@T=\min(H_n,L)@@，用坐标删除形式的 Efron–Stein 不等式把 @@M@@\operatorname{Var}(T)@@ 归结为 @@M@@\sum_i\mathbb E D_i^2@@，其中 @@M@@D_i@@ 是删去第 @@M@@i@@ 条子句（保留其余子句原时间指标）带来的延迟。新引擎是一个势函数（potential）：对任意指派集合 @@M@@S\subseteq\{0,1\}^u@@，令 @@M@@q_j(S)@@ 为 @@M@@j@@ 条随机 proper 2-子句”杀死”@@M@@S@@（即无成员满足全部子句）的概率，@@M@@P_d(S)=\sum_{j<d}q_j(S)@@ 有界且随 @@M@@S@@ 缩小而增。基于冻结坐标（frozen coordinate）计数 @@M@@b@@ 的精确杀伤公式 @@M@@h_a(S)=(b)_a/(2^a(u)_a)@@，一条 2-子句与一条 3-子句的杀伤概率满足 @@M@@h_2^{3/2}\le 3h_3+u^{-3}@@；对 @@M@@j@@ 求和得势漂移引理：@@M@@q_d(S)^{3/2}@@ 被 @@M@@P_d@@ 在一条随机 3-子句下的期望增量控制。再把固定 @@M@@C_i@@ 的三个变量称为根（root），其余子句按与根的接触分为普通、测试（test）与碰撞（collision）三类；暴露静态信息后，测试子句的非根部分仍是独立的 2-子句。若恢复 @@M@@C_i@@ 会破坏可满足性，则每个可用根的翻转都必须被该根的测试子句拦截，无碰撞时给出三个独立测试同时杀伤当前非根解集 @@M@@S_m@@ 的概率 @@M@@p_m^3@@。势漂移则把”@@M@@S_m@@ 停留在高水平”的总时间压到 @@M@@O(d^{3/2})@@。关键的调制技巧在于条件作用分层：剩余时长的估计需要知道删除事件是否已发生（用较大 @@M@@\sigma@@ 域 @@M@@\mathcal H_m@@），但其上界 @@M@@W_m@@ 只依赖较小的 @@M@@\sigma@@ 域 @@M@@\mathcal G_m@@，故可与给定 @@M@@\mathcal G_m@@ 的独立测试概率相乘；恒等式 @@M@@3-3/2=3/2@@ 使乘积恰好落回势函数可积的范围，得无碰撞时 @@M@@\mathbb E[D_i^2\mid\mathcal E]\le 2K^2d^3@@。最后用根入射计数 @@M@@d@@ 的一致有界矩与碰撞稀有概率（@@M@@O(n^{-2})@@）平均掉碰撞情形，得 @@M@@\mathbb E D_i^2=O(1)@@，对 @@M@@i@@ 求和即 @@M@@\operatorname{Var}(T)=O(n)@@；再用一阶矩尾部 @@M@@2^n(7/8)^m@@ 以指数速度去掉截断。下界由 Wilson 分位数分离定理：@@M@@3/4@@ 与 @@M@@1/4@@ 水平的整数分位点相距 @@M@@\ge c_0\sqrt n@@，取两个独立副本比较即得 @@M@@\operatorname{Var}(H_n)\ge c_0^2n/16@@。
本文主结果暂无形式化证明，OpenAI 官方声明未经形式化的结果可能有问题，请以社区核验为准。文中完整重证并沿用了同族姊妹篇（一般 @@M@@k@@ 方差）的删除–根测试框架，仅替换 @@M@@k=3@@ 处关键的占位估计，从而闭合对数空隙；姊妹篇则提供 @@M@@k\ge4@@ 的 @@M@@\Theta_k(n)@@ 对照结果，两文合成”每个固定 @@M@@k\ge3@@ 方差均为 @@M@@\Theta_k(n)@@“的完整图景。作者将解决可满足性猜想的优先权归于 Carenini 的并发工作；本文处理的是更精细的涨落问题。
针对《Linear Variance of the Random 3-SAT Hitting Time》，基于论文原文（定理 1.1、引言及 §2 势函数引理）
问 1：去掉对数损失的关键新招是什么？
（答：势函数漂移引理（§2，引理 2.2）。对有 b 个冻结坐标的指派集 S，杀伤概率有精确公式 h_a=(b)_a/(2^a(u)_a)，由此得一条比较不等式 h_2^{3/2} ≤ 3h_3 + u^{-3}；再经 Jensen 与增量恒等式把 q_d(S)^{3/2} 控制在 P_d 于一条随机 3-子句下的期望漂移里。姊妹篇的占位估计在此处每次对数级损失，势函数把损失改成一次性、可和的漂移——这是全文唯一真正新的引擎，也是最值得复核的引理。）
问 2：方差上界证明里最脆弱的一步在哪？
（答：条件作用的分层（引言 §1.2）。剩余时长的估计需要知道删除事件是否已发生（大 σ-域 H_m），但其上界 W_m 只依赖小 σ-域 G_m，这才允许与”给定 G_m 时三个根的测试子句独立杀伤”的概率相乘；恒等式 3−3/2=3/2 使乘积恰好落回势函数可积范围，得条件平方延迟 O(d³)。若 W_m 的可测性声明差一点——比如暗中依赖了 H_m——独立性即失效，整个 E[D_i²]=O(1) 就立不住。这是测度论记账最容易埋雷的地方。）
问 3：k=3 的特殊性在哪、结论能推广吗？
（答：三文字子句给出恰三个根、三个独立测试族，指数 β=3/2 与之配套；碰撞子句（同时触及两个根）概率 O(n^{-2})，靠根入射计数 d 的一致有界矩平均掉。k≥4 已由姊妹篇用同一框架证 Θ_k(n)；k=2 蕴涵图机制另案。论文未讨论 CLT（H_n 中心化后是否高斯）——方差定理之后最自然的问题。）
问 4：与已有工作相比新意与边界何在？
（答：上界 Var ≤ Cn 是新贡献：姊妹篇在 k=3 只有 O(n log n)，Carenini 的并发结果是 O(n^{1+2/k})（k=3 时 n^{5/3}）——本文的界严格更锐。下界不新：由 Wilson 2002 的分位数分离定理短推导而来（论文如实注明）。合起来窗口宽度 Θ_η(√n) 被精确钉死，这比 Friedgut 的 o(n) 与 Wilson 的 Ω(√n) 都完整。）
问 5：AI 生成证明最可能出错的模式？
（答：一是”必要测试”的逻辑——若恢复被删子句破坏可满足性，则每个可用根的翻转都必须被该根的测试子句拦截，这类”每个都必须”的组合推理在随机暴露下容易漏掉一两种构型（尤其碰撞情形的分类）；二是截断的移除——H_n 截断在 10n 后靠一阶矩尾部 2^n(7/8)^m 指式衰减复原，若尾部界在中心附近不够快，截断方差与真方差的差就不容忽略。）
问 6：固定中心窗口的界为什么不够、这文如何绕开尾部？
（答：引言明言：方差还依赖尾部，固定中心窗口界（如 Carenini 的 O(n/log n)）不足以给方差界。本文的做法是不围绕阈值、而围绕有限尺寸期望集中：删子句的延迟平方对所有时间指标一致控制，尾部由指数一阶矩单独处理——”先截断、再集中、后去帽”的三段式是方差界的正确骨架。）
问 7：谁会用到它？
（答：与姊妹篇合成”一切固定 k≥3 方差均为 Θ_k(n)”的完整图景，给随机 SAT 相变的精细理论立下基准；研究中心极限定理、窗口内概率剖面、以及算法在相变附近行为的人从此知道正确的涨落尺度是 √n。）
总评
这是一篇目标单一、执行干净的”闭空隙”论文：新引擎只有势函数一处，其余是姊妹篇框架的忠实重用；最大风险也正集中在那处恒等式 h_2^{3/2}≤3h_3+u^{-3} 的系数与分层条件化的可测性细节上——但骨架小，社区核验成本低。