结果族 103：Exact derandomization of logarithmic space:
@@M@@\mathsf L=\mathsf{RL}=\mathsf{BPL}@@· 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
一个只带一张便签记忆的机器人走迷宫，每到岔口就掷硬币选路。复杂性理论问：硬币能省掉吗？这篇论文给出彻底的肯定答案：存在同样只带一张便签、从不掷硬币的机器人，能完成硬币机器人的一切任务——随机性在”便签级记忆”下是完全免费的。
关键词卡片
@@M@@\mathsf L@@）：内存只有输入长度对数倍的确定性计算模型。@@M@@\mathsf{RL}/\mathsf{BPL}@@）：掷硬币机器”只在回答’是’时可能出错”与”两种回答都可能出错”两档。看个具体例子
核心是条数值化的定理：确定性机器能算出每个输入的接受概率 @@M@@p(x)@@，误差 @@M@@\le(n+2)^{-d}@@。取 @@M@@d=3@@：误差 @@M@@\le 1/8@@；而随机机器承诺接受概率要么 @@M@@\ge 2/3@@ 要么 @@M@@\le 1/3@@，两者相隔 @@M@@1/3@@，远大于 @@M@@1/8@@，所以拿算出的数与 @@M@@1/2@@ 比大小即可正确判定。
为什么值得关心
@@M@@\mathsf L@@、@@M@@\mathsf{RL}@@、@@M@@\mathsf{BPL}@@ 三者是否相等是复杂性理论的基础问题之一，本文不仅给出肯定回答，还附上带显式时空界的编译器。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读的”便签机器人”精确化：对象是一台只带对数级内存、运行多项式时间的机器，它在每个岔口掷硬币选下一步；操作是把它在整个输入上的随机游走行为完整刻画出来。要回答的问题：能否造一台同样节省内存、从不掷硬币的机器，完成硬币机器的一切任务。
第二级台阶
复杂性类语言：L 指确定性对数空间多项式时间计算；RL 与 BPL 分别指单侧错误与双侧错误版本。机器在固定输入上的运行可画成分支程序——一张状态转移图，其接受概率 p(x) 就是图上随机游走到达接受态的概率。dyadic 有理数指分母为 2 的幂的有理数，是机器能逐位输出的数。
第三级台阶
| 主定理 L=RL=BPL 的内核是一条逼近定理：对每个固定的随机机器与精度指数 d≥1，存在统一的确定性转换器，对每个输入 x 输出 dyadic 有理数 z_x，使 | z_x−p(x) | ≤(n+2)⁻ᵈ，且只用 O(log n) 工作空间与多项式时间。”多项式时间”假设保证配置图有限且层级构造在 O(log n) 步收尾；取 d=3 时误差不超过 1/8，远小于 BPL 承诺的 1/3–2/3 接受概率间隙，与 1/2 比大小即得正确判定。定理还延伸到承诺问题版本，并给出输出显式时间空间界的编译器。 |
证明了 @@M@@\mathsf L=\mathsf{RL}=\mathsf{BPL}@@：多项式时间的对数空间随机计算，无论单侧错误还是双侧错误，都能被确定性对数空间 (logarithmic space) 机器等价模拟，并给出带显式多项式时间界的有效编译器，彻底解决该去随机化 (derandomization) 问题。
复杂性理论用 @@M@@\mathsf L@@、@@M@@\mathsf{RL}@@、@@M@@\mathsf{BPL}@@ 分别刻画确定性、单侧错误 (one-sided error) 与双侧错误 (two-sided error) 的对数空间多项式时间计算。平凡包含 @@M@@\mathsf L\subseteq\mathsf{RL}\subseteq\mathsf{BPL}@@ 成立，真正的难题在反方向：随机硬币究竟能否省掉。与 @@M@@\mathsf{P}@@ 对 @@M@@\mathsf{BPP}@@ 的经典问题不同，空间版本此前连把 @@M@@\mathsf{BPL}@@ 压回 @@M@@O(\log n)@@ 都做不到，通用技术只能给出略大的确定性空间上界。近年 Pyne–Raz–Zhan 提出的”普适确定性估计”路线，给出一台能统一逼近分支程序 (branching program) 接受概率的确定性算法；本文明确以它为先声，并把这条路线推进到终点。
主定理：@@M@@\mathsf L=\mathsf{RL}=\mathsf{BPL}@@。核心是”固定逆多项式精度”的概率逼近定理：对每个固定的随机对数空间多项式时间机器 @@M@@\mathcal M@@ 与精度指数 @@M@@d\ge 1@@，存在统一的确定性转换器 (transducer)，在每个长度 @@M@@n@@ 的输入上输出 dyadic 有理数 (dyadic rational) @@M@@z_x\in[0,1]@@，使 @@M@@|z_x-p_{\mathcal M}(x)|\le(n+2)^{-d}@@，其中 @@M@@p_{\mathcal M}(x)@@ 是接受概率；转换器只用 @@M@@O(\log(n+2))@@ 工作空间与多项式时间。取 @@M@@d=3@@，误差 @@M@@\le 1/8@@，与阈值 @@M@@1/2@@ 比较即可在 @@M@@1/3@@ 与 @@M@@2/3@@ 的接受概率间隙上正确判定，故 @@M@@\mathsf{BPL}\subseteq\mathsf L@@；另两个包含是平凡的（确定性机器可忽略硬币，@@M@@\mathsf{RL}@@ 重复两次即放大成 @@M@@\mathsf{BPL}@@）。论文进一步证明承诺问题 (promise problem) 版 @@M@@\mathsf{PromiseBPL}=\mathsf{PromiseL}@@，精度可作为输入的一部分给出，并且当 @@M@@p_{\mathcal M}(x)\ge(n+2)^{-c}@@ 时能在对数空间输出经过认证的接受计算。最后是有效编译器定理：给定机器描述 @@M@@M@@ 与正整数 @@M@@a,b@@，算法输出确定性机器 @@M@@D_M@@ 及显式常数 @@M@@K,H,c@@——只要 @@M@@M@@ 满足声明的 @@M@@(n+2)^a@@ 步与 @@M@@b\lceil\log(n+2)\rceil@@ 比特界，@@M@@D_M@@ 就判定同一语言，且每次执行至多用 @@M@@K\log(n+2)@@ 个工作比特与 @@M@@H(n+2)^c@@ 次基本位操作。
证明是一条自下而上的长链。第一步，把随机机器在输入 @@M@@x@@ 上的运行写成有限配置图 (configuration graph)：转移矩阵 @@M@@S@@ 严格前向（@@M@@S(x,y)=0@@ 除非 @@M@@x<y@@）、行和不超过 1，接受概率是线性方程组的解 @@M@@p_0=(I-S)^{-1}e@@，于是去随机化等价于在对数空间内确定性逼近这个数。第二步是纠正—复制层级 (correction and copy hierarchy)：利用恒等式 @@M@@I-D=(I+E)(I-C)@@，每阶段构造修正项 (correction) @@M@@E@@ 把转移质量搬入奖励 (reward)，使残余矩阵 @@M@@D=C-E+EC@@ 的元素在”好列”上大幅缩小；再用 @@M@@D_0@@ 份复制 (copies) 把残余大项分流，全部元素从 @@M@@f@@ 压到 @@M@@f/2^H@@，而活跃顶点数每阶段至多翻倍。@@M@@L=O(\log n)@@ 步后转移行和降到 @@M@@1/16@@ 以下，搬运出的奖励 @@M@@W_L@@ 便逼近 @@M@@p_0@@。修正项需要知道哪些列”过载”，这由随机探测器 (detector)——对采样行的秩统计量取期望——判定。第三步，整个随机环境只需 @@M@@O(\log n)@@ 个随机比特：若干独立的秩通道 (rank channel) 是有限域 @@M@@\mathbb F_P@@ 上随机矩阵实现的哈希，顶点 @@M@@y@@ 在速率 @@M@@a@@ 被保留的概率 @@M@@\pi_a@@ 与 @@M@@a@@ 同阶；论文构造原子 (atom) 表（分箱、修正、探测器得分），使其在保留事件下的条件期望 (conditional expectation) 恰好等于层级中的精确量，且行门与入门保证每行、每列只有常数个非零端口。第四步是递归估计：每个任务带统计预算 @@M@@M@@，误差以对环境的 8 阶积分矩度量并按 @@M@@C_b2^{-p}@@ 归纳控制；关键技巧是”加法调度”——不做一次长平均，而是对相邻预算估计之差施以长度递增的条件平均随机游走 (conditional walk)，其谱隙 (spectral gap) 一致，条件均值伸缩相消、噪声指数衰减，过细的贡献则整体省略。最后收尾：条件化到指定起点损失因子 @@M@@N=2^{O(\log n)}@@，由 8 阶矩加 Markov 不等式支付；随后穷举全部 @@M@@2^{O(\log n)}@@ 个环境编码（原始盐比特串与域矩阵元素），逐个确定性算出估计值的 dyadic 数码再取中位数 (median)——因超过四分之三的环境足够准，中位数必落在误差 @@M@@(n+2)^{-d}@@ 之内。编译器一节补上显式界：先造自带时间与空间上限的固定解释器 (interpreter) @@M@@U@@，把逼近定理作用于 @@M@@U@@ 得到固定的确定性判定库 @@M@@A@@；对每个源机器用长度 @@M@@N_{\mathrm{pad}}=2^{PB_n}@@ 的虚拟填充输入把它无损嵌入 @@M@@U@@ 的上限（接受概率精确不变），@@M@@D_M@@ 靠回调从真实输入按需重生成虚拟符号；最后用构型计数 (configuration counting) 导出空间与时间的显式联立界。
本结果暂无形式化证明，OpenAI 官方亦声明”未经形式化的结果可能有问题”，请以社区核验为准。该手稿（2026 年 9 月 23 日版）是结果族 103 中唯一一篇，没有族内姊妹篇互相支撑；其正确性依赖”环境—层级—原子—估计—指纹—算术—实现—编译器”这一内部自洽的长链条，任何一环（尤其是论文中按严格顺序选择的众多固定常数）出错都会波及主定理，读者宜以同行评议结论为准。
问 1：证明中最关键、也最脆弱的一步是什么？
答：纠正—复制层级与原子表的对接。层级阶段用恒等式 I−D=(I+E)(I−C) 逐级压缩残余矩阵元素，修正项 E 需要”哪些列过载”的信息，由随机探测器（采样行的秩统计量）给出；原子表（分箱、修正、探测器得分）必须使保留事件下的条件期望恰好等于层级中的精确量。这个”恰好”匹配是估计无偏性的根基，也是最易藏错的一环。
问 2：递归估计里”加法调度”为什么是关键技巧？
答：对每个统计任务直接做一次长平均会因谱隙退化而失控；论文改为对相邻预算估计之差施以长度递增的条件平均随机游走，其谱隙一致，条件均值伸缩相消、噪声按指数衰减，过细贡献整体省略。误差以 8 阶积分矩度量并按 C_b·2^{−p} 归纳控制——这一步决定估计能否在有限预算内收敛到 (n+2)^{−d}。
问 3：机器的多项式时间界为什么不能去掉？
答：转移矩阵 S 严格前向、行和不超过 1，接受概率写成 p₀=(I−S)⁻¹e 的线性方程组解，都依赖步数有界（如 (n+2)^a 步）——它保证级数有限、层级步数为 O(log n)；若运行超多项式，配置图无界，整套逼近无从谈起。论文未讨论去掉时间界的情形。
问 4：与已有工作相比真正的新意是什么？
答：与 P 对 BPP 不同，空间版本此前连把 BPL 压回 O(log n) 都做不到，通用技术只能给出略大的确定性空间上界；Pyne–Raz–Zhan 的普适确定性估计路线给出统一逼近分支程序接受概率的算法，本文明确以它为先声并推进到终点：固定逆多项式精度、对数空间、多项式时间，从而 L=RL=BPL 彻底落地。
问 5：这个结果最可能以什么方式出错？
答：典型风险是长链条上的常数次序：论文强调众多固定常数须按严格顺序选择，任何一处循环引用即崩；其次，条件化到指定起点损失因子 N=2^{O(log n)} 靠 8 阶矩加 Markov 不等式支付，矩的阶数与常数是否足够紧凑值得逐条复核。本文未形式化，且是结果族 103 中唯一一篇，没有姊妹篇互证。
问 6：最后一步为什么穷举环境再取中位数就能去随机化？
答：整套随机环境只用 O(log n) 个随机比特，故编码总数 2^{O(log n)} 是多项式个；估计的 8 阶矩保证超过四分之三的环境给出足够准的估计，于是逐个确定性重算 dyadic 数码再取中位数，必然落在 (n+2)^{−d} 误差内——确定性模拟器由此诞生。
问 7：谁会用到它？
答：复杂性理论教材与研究者：对数空间随机类的三合一坍缩是基础问题的收官；依赖随机游走的对数空间算法（如无向连通性等）原则上都可换成显式编译出的确定性机器；形式化社区则获得一个高价值的验证标的。
总评
解决了与 P=BPP 同宗的基础开问题，还附上显式编译器，分量可观；最大风险是”环境—层级—原子—估计—算术—编译器”长链条完全依赖内部自洽且未经形式化，单环失守即全盘皆输。