结果族 104：Quasipolynomial algorithms for mean-payoff, stochastic and parity games · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
还是”在图上永远走下去、比长期平均输赢”的二人博弈，这次只谈钱。此前的最好算法有个别扭之处：耗时按赌注的数值计费——写下一百万只需 20 个比特，机器却要干一百万量级的活。这篇论文第一次做到”按书写长度收费”：权重用二进制写下共用 @@M@@L@@ 个比特，求解就只需 @@M@@2^{O((\log L)^2)}@@ 步，顺带还能算出每个起点的精确输赢值。
关键词卡片
@@M@@2^{O((\log L)^2)}@@，比多项式略慢、比指数远远快看个具体例子
环上两点 A、B，边权一正一负，恰好打平还赚一点：
公式卡
@@M@@w(A\to B)=+1000000,\quad w(B\to A)=-999999\ \Rightarrow\ \text{环平均}=\tfrac{1000000-999999}{2}=\tfrac12\ge 0@@
于是 A 属于 Max 的取胜集。写这两个数只需约 42 个比特：旧算法的时间含一个 @@M@@\propto W\approx 10^6@@ 的因子，本文按 @@M@@L\approx 42@@ 计费，只花 @@M@@2^{O((\log 44)^2)}@@ 次位操作——数值再大十亿倍，位数也只多约 30，耗时几乎不动。
为什么值得关心
该问题四十多年悬在 NP∩coNP 而无多项式算法，这是首个按位长计的确定性拟多项式解法，也是同族另外两篇的发动机。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里”按赌注数值计费还是按书写长度收费”的对比，翻译过来是：博弈的舞台仍是一张带边权的地图，两位玩家轮流挑下一条边、永不停歇；要判定的是”从某点出发，先手能否保证长期平均每步不亏”。旧算法的账单与边权的数值大小成正比，而数值是二进制位数的指数倍；新算法的账单只与把这些数字写下来所需的笔墨总量挂钩。
第二级台阶
用本科术语说：平均收益博弈由有限有向图、顶点归属划分与整数值边权 w 给出；一条无穷对局 π 的平均收益 MP_w(π) 定义为前 T 步权重平均当 T 趋于无穷的下极限。位置策略是只看当前顶点的选边规则，经典结果是双方都拥有位置最优策略，于是”平均能否非负”这一阈值问题落在 NP∩coNP 中。L 指图、所有权与全部二进制权重编码的总长度。
第三级台阶
定理正是在这套编码语境下陈述：权重是任意带符号的二进制整数，自环与平行边都被允许，数值不设上限——这份自由恰使一切按数值计费的界在 L 面前指数爆炸，也挡住了从奇偶博弈拟多项式算法的直接移植（经典归约方向相反）。结论是：存在一致的确定性算法，至多用 2 的”对数平方”级次位操作，一次性精确输出全部取胜顶点；再经归约，同一界内还能算出每个起点的精确有理值与双方全局最优的位置策略。
给出任意带符号二进制整数边权的平均收益博弈零阈值取胜集的确定性算法，用时 @@M@@2^{O((\log(L+2))^2)}@@ 次位操作；经归约还能在同界内算出每个顶点的精确有理值与双方全局最优位置策略。本篇是结果族 104 另两篇的算法基石。
平均收益博弈（mean-payoff game）中 Max 与 Min 轮流选边，争夺无穷行走的长期平均权重。Ehrenfeucht 与 Mycielski（1979）证明位置最优策略存在，使阈值问题落入 @@M@@\mathrm{NP}\cap\mathrm{coNP}@@，但多项式可解性至今开放。Zwick 与 Paterson（1996）的经典算法是伪多项式（pseudopolynomial）的：时间随最大绝对权重 @@M@@W@@ 增长，而 @@M@@W@@ 以二进制编码时其数值可远大于输入长度本身。此后的能量式提升（Brim 等 2011，@@M@@O(|E|nW_0)@@）、加速势更新、Kozachinskiy 的 @@M@@n^{O(1)}2^{n/2}@@ 等结果要么仍带数值因子，要么是随机界（Björklund–Vorobyov 的 @@M@@2^{O(\sqrt{n\log n})}@@）。奇偶博弈自 2017 年起的拟多项式算法也无法直接转移：经典归约方向是从奇偶到平均收益，而非相反。本篇首次对完整二进制输入长度给出确定性拟多项式界，成为随机篇与奇偶篇共同的方法源头。
定理（Theorem 1.1）：一致的确定性算法对每个带符号二进制整数边权（允许自环与平行边）的输入，精确输出零阈值取胜集 @@M@@U=\{v:\exists@@ Max 策略 @@M@@\sigma\ \forall@@ Min 策略 @@M@@\tau,\ \MP_w(\pi_{v,\sigma,\tau})\ge0\}@@，对手可用任意历史相关策略；总代价至多 @@M@@2^{C(\log_2(L+2))^2}@@ 位操作，含预处理、精确算术、递归与输出。论文摘要与引言另述：经归约可在同界内计算每个出发顶点的精确有理值并给出双方全局最优的位置策略（positional strategy），并把方法用于能量博弈（energy game）初始信贷判定与热带可行性（tropical feasibility）等场景（对应第 7–9 节，本文未逐节展开）。
第一步是整数圈扰动（integer cycle perturbation，源自 Björklund–Vorobyov）：令 @@M@@\widehat w(e)=(n+1)w(e)+1@@，则长 @@M@@\ell\le n@@ 的简单圈（simple cycle）的变换和为 @@M@@(n+1)c+\ell@@（@@M@@c@@ 为原始圈和），永不为零且符号恰对应 @@M@@c@@ 的正负。定义势算子 @@M@@F_i(z)@@ 为 @@M@@\widehat w(e)+z_j@@ 在属主顶点处的最大或最小，它单调且满足平移恒等式 @@M@@F(z+t)=F(z)+t@@。由同批的随机化姊妹篇导入有限盒（finite box）理论：盒内一切下解（subsolution）@@M@@\le@@ 盒解 @@M@@h\le@@ 一切上解，@@M@@h@@ 是裁剪算子的唯一不动点，朴素迭代至多 @@M@@1+\sum_i(u_i-A_i)@@ 次求值。取宽 @@M@@D_0\ge64(n+1)(W+1)@@ 的盒：从盒内沿取等边行走，@@M@@n@@ 步内必触界（否则圈出变换和为零的简单圈），每个坐标离某侧边界至多 @@M@@nW@@，故 @@M@@h@@ 落在两条带内；带上允许边构成的图里简单圈的原权和分别非负、至多 @@M@@-1@@，对任意前缀逐圈消去即得估计——高带恰是 Max 的取胜集，低带上 Min 可强制上极限平均 @@M@@\le-1/n@@。
第二步不求 @@M@@h@@，而把”每个顶点属于哪条带”改写成同时标记（simultaneous labelling）：支撑质量（mass）至多 1 的下解证人（witness）要求近上界的坐标标 @@M@@+@@，上解证人要求近下界的坐标标 @@M@@-@@，两类主张由盒比较定理保证不冲突。递归过程 @@M@@\Label(A,D,a,b)@@ 先降后升移动整数枢轴 @@M@@k@@：每次窄盒（宽 @@M@@q=D/128@@）子调用返回符号，被标反向的坐标向该方向移动一步 @@M@@p=D/4096@@；证人按”峰值偏差对齐子盒边界”平移并裁剪，只留峰值附近的支撑。受保护一方的证人峰值全程不动——差距为零的坐标被子调用锁定，其余坐标每次至多挪 @@M@@p@@、追不上峰值。枢轴停住时，最后一次不动的调用成为确定性证书：仍有主张的对方证人必有超过 @@M@@3/4@@ 的质量聚在峰值附近，否则它会迫使枢轴再动。随后一次半宽调用给这些大质量坐标定性，按”得势方 @@M@@\times4/5@@、失势方 @@M@@\times8/5@@“重配质量：每个乘积 @@M@@a_ib_i@@ 增大 @@M@@\rho=32/25@@，而未决证人的支撑质量仍小于 @@M@@8/5-\frac45\cdot\frac34=1@@，可在原盒继续递归。当所有 @@M@@a_ib_i>1@@（质量基例）或 @@M@@D<4096@@（宽度基例，直接迭代收尾）时返回。
第三步计数。定义秩 @@M@@R=d+B(\mu)@@（@@M@@D=2^d@@，@@M@@\mu=\min_ia_ib_i@@）：每个孩子都使 @@M@@R@@ 严格下降，两趟中的窄调用与重配后的延续调用都消耗预算 @@M@@B@@，唯一保预算的孩子是半宽调用、把 @@M@@d@@ 减一。初始 @@M@@B_0=O(\log n)@@、@@M@@d_0=O(L)@@；分支只出现在消耗预算的位置（每节点至多 @@M@@2048n+3@@ 个），调用总数 @@M@@\le\sum_\ell\sum_j\binom{\ell}{j}s^j=2^{O((\log_2(L+2))^2)}@@，配合每次调用的多项式位成本即得定理。
本篇是族 104 的基石论文：随机篇把其第 4–5 节的标记递归推广到折扣算子，奇偶篇把它作为黑箱求解器调用。本篇自身仅从随机化姊妹篇导入有限盒比较引理（其定义 2.2、引理 2.3–2.4），确定性递归与计数独立完成。暂无形式化证明；OpenAI 官方声明未经形式化的结果可能有问题，请以社区核验为准。
问 1：证明里最关键也最脆弱的一步是什么？
（答：枢轴停止时的”确定性证书”。递归先降后升地移动枢轴 k，当它停住，最后一次不动的子调用必须证明：仍有主张的对方证人必有超过 3/4 的质量聚在极值附近，否则那次调用本会迫使枢轴再动。引言明言这是”key deterministic certificate”——整篇的去随机化全押在这个静止论证上，最值得逐行核验。）
问 2：既然盒解 h 落在两条带里，为什么不直接迭代求 h？
（答：因为朴素迭代次数与盒宽数值 D 成正比，而宽 D₀≥64(n+1)(W+1) 对二进制输入本身就是 L 的指数。算法的全部意义在于绕开数值宽度：只问”每个坐标被迫贴哪条边界”，用证人质量与重赋权把数值信息换成对数级的组合预算。）
问 3：整数圈扰动 ŵ(e)=(n+1)w(e)+1 起什么作用？可否去掉？
（答：它使每个长至多 n 的简单圈的变换和为 (n+1)c+ℓ，永不为零且符号恰随原圈和 c——这保证沿取等边行走 n 步内必触盒界，两条带的胜负含义才成立。去掉加一的平移项，零和圈会让论证失效，这是承重墙而非装饰。）
问 4：与既有工作相比真正的新意是什么？
（答：Zwick–Paterson 与能量式算法都带数值因子；Björklund–Vorobyov 的 2^{O(√(n log n))} 是随机算术界且不许平行边；奇偶博弈的拟多项式算法因归约方向相反（奇偶归约到平均收益）无法移植。本文首次对完整二进制长度给出确定性拟多项式位界。）
问 5：这类 AI 生成证明最可能在哪里出错？
（答：两处。一是质量重配的常数账本：得势方 ×4/5、失势方 ×8/5、乘积因子 32/25、未决支撑质量 <1 等不等式环环相扣，一个常数松动全局坍塌；二是秩 R=d+B(μ) 严格下降与”唯一保预算孩子减半宽度”的组合计数。此外有限盒比较定理（定义 2.2、引理 2.3–2.4）是从随机化姊妹篇进口的，源头有失则两篇同倒。）
问 6：这个结果谁会接着用？
（答：同族奇偶篇直接把它当黑箱求解器；论文第 7–9 节还把同一界推广到每点精确有理值与全局位置策略、能量博弈初始信贷判定，以及热带可行性与热带秩检验。它也是逼近悬置四十余年的”NP∩coNP 是否多项式可解”的第一级台阶。）
总评
这是结果族 104 的发动机：首个按位长计费的确定性拟多项式算法，分量极重；最大风险在于其正确性一半靠自身递归、一半靠姊妹篇的有限盒理论，且常数密集的组合论证正是机器证明的高发事故区。