结果族 113：Approximate counting and entropy of perfect matchings · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
联谊会上有 2n 个人，任意两人都可以结对，要把所有人两两配对——找出一种配法早就是教科书算法，但”数清一共有多少种配法”却被证明是 #P 完全的，几乎无望精确。本文给出随机近似算法：像”标记再捕”估计湖里有多少鱼一样，在多项式时间内给出相对误差 ε、成功率 1−δ 的估计，而且根本配不成对时必然如实输出 0。这补上了 1989 年提出、悬了近四十年的最后一块拼图。
关键词卡片
看个具体例子
把立方体的 8 个顶点、12 条棱看作一张图：它共有 9 个完美匹配（图中红色 4 条”斜棱”是其中之一）。定理的数字版：@@M@@\Pr[(1-\epsilon)\cdot 9\le\hat Z\le(1+\epsilon)\cdot 9]\ge 1-\delta@@——比如取 ε=1%，输出就落在 8.91 与 9.09 之间；若图根本无法全员结对，则每次执行都输出 0。
为什么值得关心
一般图完美匹配计数是近似计数理论的地标难题：二部图 2004 年解决、平面图早有精确解，一般图这一格被本文填上，连带指定度数、指定大小的匹配也能近似计数。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读的”标记再捕估鱼数”可以改述为：想知道一个庞大集合里有多少元素，就设计一个能近似等可能地摸到元素的随机过程，用”摸到某类元素的频率”去反推总数；再从容易数的情形出发，把目标一步步变形，每步估一个比值、最后连乘。这里的元素是”让每个顶点恰好连一条边的边集”，困难在于这类元素可能只占全体匹配中指数小的一份，随机过程很难摸到。
第二级台阶
用本科术语精确化。完美匹配数 Z(G) 的精确计算即使二部图也是 #P 完全的；FPRAS 指这样的随机算法：以多项式于输入长度、ε⁻¹ 与 log δ⁻¹ 的时间，输出落中真值相对误差 ε 区间的概率至少 1−δ。马尔可夫链蒙特卡洛靠设计随机游走来近似均匀采样；退火指从易采样的加权分布逐级收紧到目标分布、逐级估配分函数之比。
第三级台阶
定理在这样的语境下陈述：对任意有限简单无向图 G，先用 Edmonds 算法做确定性存在性检测——Z(G)=0 时必然输出零，挡住”无解还瞎猜”；否则算法以所述多项式位时间输出 ̂Z，落中 (1±ε)Z(G) 的概率至少 1−δ。关键的硬假设只有”有限简单无向图”这一输入模型（文中明言不支持压缩的边重数表示），而结论还附带推论：指定顶点度的边子集（f-因子）与指定大小的匹配同样可近似计数并在全变差意义下近似均匀采样。导读中”近四十年的最后一块拼图”，至此严格合缝。
对任意有限简单无向图给出完美匹配计数的全多项式随机逼近格式（FPRAS），时间多项式于输入长度、@@M@@\varepsilon^{-1}@@ 与 @@M@@\log\delta^{-1}@@，无完美匹配时确定性输出零，正面解决了 Jerrum–Sinclair 在 1989 年提出的一般图难题。
图 @@M@@G@@ 的完美匹配（perfect matching）是让每个顶点恰好被一条边覆盖的边集，记其数目为 @@M@@Z(G)@@。”找到一个”与”数清全部”难度悬殊：Edmonds（1965）给出多项式时间求最大匹配的算法，而 Valiant（1979）证明即使在二部图上精确计数也是 #P 完全（#P-complete）的——即 0-1 矩阵的永久积（permanent）；只有平面图可由 Kasteleyn 的 Pfaffian 方法精确求解。近似计数须区分三个问题：Jerrum 与 Sinclair（1989）对”所有匹配的总数”给出 FPRAS；Jerrum、Sinclair、Vigoda（JSV，2004）对二部图完美匹配（非负矩阵永久积）给出 FPRAS；而一般图完美匹配的近似计数由 Jerrum–Sinclair 1989 年论文第 7(i) 节明确提出，此后近四十年是近似计数的标杆难题。卡点很明确：完美匹配可能只占匹配空间指数小的一份，”完美+近完美匹配”马尔可夫链的平稳质量过小；Štefankovič、Vigoda 与 Wilmes（2018）更构造出图例，证明任何 JSV 型链在这种图上要么平稳概率指数小、要么混合（mixing）指数慢。因此必须更换状态空间与能量比较方式。
主定理（Theorem 1.1）：存在一致的经典随机算法，输入图 @@M@@G@@ 与有理数 @@M@@0<\varepsilon<1@@、@@M@@0<\delta<1/2@@，输出非负有理数 @@M@@\widehat Z@@，满足
@@M@@D\Pr\bigl[(1-\varepsilon)Z(G)\le\widehat Z\le(1+\varepsilon)Z(G)\bigr]\ge 1-\delta,@@
且最坏情形比特时间多项式于输入编码长度、@@M@@\varepsilon^{-1}@@、@@M@@\log\delta^{-1}@@；若 @@M@@Z(G)=0@@，算法必然输出零（先以 Edmonds 算法做确定性存在性检测）。第 10 节还推出推论：规定每顶点度数的边子集（经 Tutte 归约到 @@M@@f@@-因子，f-factor）与指定大小 @@M@@k@@ 的匹配（添加 @@M@@n-2k@@ 个哑点）这两族对象，同样可近似计数，并可在全变差（total variation）意义下近似均匀采样，且采样器每次执行都返回可行对象。
算法骨架沿用 JSV 式退火（annealing）：从完全图 @@M@@K_V@@ 出发——其匹配数 @@M@@(n-1)!!@@ 精确已知——把非边的活动度按 @@M@@b^{-j}@@（@@M@@b=1+1/n@@）逐级压低，估计相邻两级配分函数之比再连乘；级数 @@M@@K@@ 足够大后，用到非边的匹配总偏差被压入 @@M@@\varepsilon@@ 之内。采样的一大障碍是完美匹配质量塌缩，作者引入顶点缩放（vertex scaling）@@M@@\lambda_{ij}=w_{ij}s_is_j@@ 维持平衡（balanced）条件：各顶点处两洞配分比（two-hole partition ratio）@@M@@g_\lambda(ij)@@ 的行最大值始终落在 @@M@@[1/4,1]@@。
为让一次样本同时给出比值与两洞信息，作者把图放大：每条逻辑边替换为长 @@M@@4p+1@@ 的带权路径，活动度相邻成对相等、由端点向中心递减，使实路径匹配与逻辑完美匹配一一对应且权只差公因子；再按瓶颈相似度（bottleneck similarity，两顶点间所有路径上最小活动度的最大值）的阈值分层构造标签树，在每个树包（bag）内添加活动度约 @@M@@h_l/D@@ 的弱团边。核心的洞界定理断言：平衡时对任意偶数洞集 @@M@@U@@ 有 @@M@@g_\lambda(U)\Phi_B(U)\le 2D_0^{|U|/2}@@，其中 @@M@@\Phi_B@@ 是配对容量（pairing capacity，两两瓶颈值乘积在所有配对上的最大值）。其证明先用两个匹配的交替叠加（alternating overlay）得到四洞不等式，再把洞沿强路径逐点搬移、以行最大值归一使误差相加而非相乘，最后对新增边参数微分配分函数。由此辅助团边至多令配分函数翻倍（膨胀因子 @@M@@I\le2@@），一次样本以至少 @@M@@1/2@@ 的概率全为实边；又在每条中心边上预留活动度 @@M@@1/D@@ 的”探针”（probe），以精确恒等式暴露两洞比值，供下一轮单遍扫描式的尺度更新。
采样器本身是全新的乘积空间链：状态是两个匹配组成的对，提议分双边换边、换色、交替圈（alternating cycle）交换三类，按 Metropolis 规则接受。能量比较不走路径拥堵定理，而是把每个交替圈按标签树自适应地四边形剖分（quadrangulation），把整圈差异写成精确的带号恒等式——每条内部对角线在两侧互补弧上的贡献恰好相消——再用编码引理（每个需求至多 @@M@@(10N)^{30}@@ 个原像）与圈交换控制语境误差。但这条两坐标不等式只控制可加函数；作者进而搭一座”梯子”：把活动度夹到 @@M@@[c^{-t},c^t]@@（@@M@@c=1+N^{-2}@@）得到一列相邻密度比不超过 2 的层，每层放 @@M@@q=32L@@ 个独立副本，底层单位活动度可由树状动态规划精确计数与精确采样；借 Efron–Stein 正交分解与槽位排序，使每对坐标的残差交互项只被记费一次，复制平均将其吸收，从而对任意函数得到谱隙（spectral gap）下界与多项式混合时间。计数阶段每级取 @@M@@S@@ 个独立样本，由 Hoeffding 不等式单次试验以至少 @@M@@0.9@@ 的概率成功，取 @@M@@10(\lceil\log_2\delta^{-1}\rceil+1)+1@@ 次独立试验的中位数即把置信放大至 @@M@@1-\delta@@。第 9 节补出完整的有限比特实现，所有参数有固定次数的多项式界。
本文暂无形式化证明，请以社区核验为准。同族姊妹篇《Entropy and Face Dimension of the Perfect-Matching Polytope》证明了完美匹配熵猜想且主结果已 Lean 形式化，并给出确定性的 @@M@@512^{-n}@@ 因子近似计数，与本篇的随机相对误差路线互补。按 OpenAI 官方声明，未经形式化的结果可能存在问题；且本文多项式指数很大，常数是为证明透明而设，并非实用运行时间。
问 1：证明里最脆弱的一环是哪里？
答：采样器的谱隙”梯子”。四边形剖分给出的带号恒等式只控制两个匹配坐标上的可加函数（Proof architecture 节明言”最初只控制可加函数”）；要得到任意函数的谱隙，必须搭一列活动度被夹住的层，每层放 q=32L 个独立副本，靠 Efron–Stein 正交分解与槽位排序保证每个坐标交互项至多被记费一次，再用复制平均吸收残差（引理 replica-gap）。若某交互项被重复计费或复制系数不够，多项式混合时间即告失守——而混合正是这个问题历史上真正的死穴。
问 2：Štefankovič–Vigoda–Wilmes 的混合下界为什么不挡住本文？
答：SVW18 的障碍是精确制导的：它只针对 JSV 型链——”完美＋近完美匹配”状态空间、Broder 提议、Metropolis 接受——在这类链上要么完美匹配平稳概率指数小、要么混合指数慢。本文干脆换状态空间：放大染色图上两个完美匹配的乘积空间，提议含双边换边与交替圈交换，能量比较不走路径拥堵定理而走带号恒等式（History 节明言区别）。这是绕开适用范围，不是推翻下界；审稿人应核对 SVW 型构造是否真能嵌入新状态空间。
问 3：与 JSV 2004 相比真正的新意是什么？
| 答：JSV 只解决二部（非负矩阵永久积），其权重学习依赖二部结构；一般图版本自 Jerrum–Sinclair 1989 年第 7(i) 节提出后悬置近四十年。本文的新部件是：顶点缩放维持行平衡（两洞配分比行最大值落在 [1/4,1]）、按瓶颈相似度分层的树包结构、以及配对容量 Φ_B 撑起的洞界定理 g_λ(U)Φ_B(U)≤2D₀^{ | U | /2}，合起来保证辅助团边至多让配分函数翻倍、一次样本以 ≥1/2 概率全为实边。 |
问 4：这个结果最可能以什么模式出错？
答：典型风险是”精确恒等式×近似估计”的交织：探针边与带号恒等式都是精确事件，但尺度更新用的是估出来的两洞比值，平衡条件如何在估计误差下逐级传播是生命线——论文特意让采样器本身不需要平衡假设（Proof architecture 末段），只在分析里用平衡传播准确性，这一分离若在某处被打破就会连锁失效。另外第 9 节的有限比特实现、编码引理每个需求至多 (10N)³⁰ 个原像的多重界，都是要逐行核对的账目。全文无形式化证明。
问 5：为什么要把每条逻辑边替换成长 4p+1 的加权路径？
答：细分一举三得：实路径匹配与逻辑完美匹配一一对应、权只差公因子；活动度从端点向中心递减、相邻可比，使瓶颈相似度的等价类能长成树包结构；再在中心边预留活动度 1/D 的”探针”，以精确恒等式暴露两洞比值供下一轮尺度更新。没有细分，平衡条件与可观测事件就无处安放。
问 6：谁会用到它？
答：直接推论已覆盖 f-因子与指定大小匹配的计数和全变差采样；更远处，Cai–Liu 把一般图完美匹配近似与八顶点模型近似挂钩，Fei–Goldberg–Lu 指出的自旋系统等价参数线也因此落进 FPRAS 区域。相比 Yi 的 hafnian 结果（需最小度 (1/2+γ)n 的密度承诺），本文对任意简单图无条件成立。
总评
这是近似计数理论近二十年最重要的落子之一，正面填上 JSV 版图的最后空格；最大风险在乘积空间链的谱隙梯子这条全新技术线上——它既无前人近似可循，也无形式化背书。