计数复杂度

破除误解：#P 不是「更细的 NP」#

把 #P 理解成「NP 的计数版」大体不错，细节会错。NP 关心的是存在性：非确定性图灵机有没有一条接受路径。#P 关心的是路径条数。若一个函数 $f$ 能由某台多项式时间非确定性机器的接受路径数给出，则 $f\in\#\mathrm{P}$。#SAT——数布尔公式的满足赋值——是典型成员，并且是 #P 完全的。

由此立刻得到：#P 至少和 NP 一样硬。只要会数，就能判断个数是否大于零，于是 NP 的判定问题可以交给一个 #P 神谕。反过来不成立：存在判定在 P 里、计数却 #P 完全的问题。完美匹配是教科书例子；生成树个数反而「碰巧」容易，Kirchhoff 矩阵树定理把它还原成行列式。同一张图上，一种计数走积和式，一种走行列式，难度可以隔着一整个复杂度类。

另一个误解是把 #P 完全当成「不能近似」。#P 完全说的是精确值。近似计数有自己的地图：FPRAS（fully polynomial randomized approximation scheme）要求相对误差 $\varepsilon$、失败概率 $\delta$，时间对输入规模、$1/\varepsilon$ 和 $\log(1/\delta)$ 都是多项式。精确困难并不自动禁止 FPRAS。杰勒姆、瓦利安特与瓦齐拉尼在 1986 年证明：对自归约的 NP 关系，近似计数与近似均匀抽样在多项式随机归约下等价。计数的算法故事，一大半是马尔可夫链，而不是穷举。

第三种误解是把 Toda 定理读成「多项式层级塌缩」。户田 1991 的定理说 $\mathrm{PH}\subseteq\mathrm{P}^{\#\mathrm{P}}$：整个多项式层级都可以在确定性多项式时间里，用一个 #P 神谕解决。它没有证明 PH 塌到某一层，它证明的是计数神谕的力量大到可以吞掉整座层级。PH 是否塌缩，仍然开放。

积和式对行列式：符号如何决定世界#

$n\times n$ 矩阵 $A$ 的行列式是 $\sum_{\sigma\in S_n}\mathrm{sgn}(\sigma)\prod_i A_{i,\sigma(i)}$，积和式去掉 $\mathrm{sgn}(\sigma)$。对 0-1 矩阵，积和式等于二部图完美匹配数。瓦利安特的归约从 #SAT 或从有向圈覆盖出发，把计数问题编码进矩阵条目。关键不在代数公式好看，而在：没有符号交替时，高斯消元那套消去与相消全部失效。

算术电路的语言把这件事说得更干净。瓦利安特后来把多项式族的复杂度收成 VP 与 VNP：行列式是 VP 的完整问题（在相当弱的归约下），积和式是 VNP 的完整问题。布尔世界的 P vs NP，在算术世界里变成「行列式能不能有效地模拟积和式」。已知的模拟需要指数大的行列式，或需要用减法把符号偷偷送回去。单调电路、无除法电路上的分离更清晰；一旦允许任意特征为零的常数和减法，界限立刻变软。这是电路复杂度与计数复杂度共用的一条前线，对象不同，相消失效的直觉相同。

模运算会改变颜色。积和式模 2 等于行列式模 2，因为 $-1\equiv 1\pmod{2}$，于是模 2 可多项式计算。模 $2^k$ 的复杂性随 $k$ 爬升；对奇数模，Valiant 已经给出硬度。计数问题对「模掉多少」极度敏感：同一个函数，模 2 可能在 P，模 7 可能 #P 硬。这不是数论游戏，它说明 #P 的硬度可以藏在一个模数里。

户田定理：一次计数查询吞掉多项式层级#

多项式层级 PH 把 NP、coNP、$\Sigma_2^p$、$\Pi_2^p$ 一层层叠上去，每一层对应多一层存在/全称交替。户田的证明分两步，至今仍是「随机性与计数如何互换」的示范。

第一步用 Valiant–Vazirani 的隔离引理：随机给 SAT 变量加哈希约束，以不可忽略的概率把满足赋值的个数压到恰好一个。于是 NP 可以随机归约到「唯一满足」这类奇偶计数问题。第二步把随机性吸收进 $\oplus\mathrm{P}$（接受路径数为奇数）和 #P 之间的关系，再用线性代数技巧把一层层交替编码成一次计数。结果是：PH 里任意一层的语言，都可以变成对某个 #P 函数的一次查询，外加多项式时间的后处理。

定理的推论比定理本身更常被引用。若 #P 函数可以在多项式时间计算，则 PH 塌缩。因此「积和式没有多项式算法」比「SAT 没有多项式算法」更强：它会压垮整座层级，而不只是 NP。反过来，今天所有「#P 大概很难」的信念，都寄生在「PH 大概不塌」这种同样未被证明的判断上。计数复杂度没有给 P vs NP 一个新的攻击面，它给了一个更狠的赌注。

与交互证明的对话在 1990 年代迅速展开。#P 在 Toda 之后看起来几乎全能，但 Lund、Fortnow、Karloff、Nisan 以及 Shamir 把 $\mathrm{IP}=\mathrm{PSPACE}$ 建立在代数计数（多项式和检验）上。计数一次是神谕，交互多次是证明。两条线都在数赋值，一个把数当成答案，一个把数当成可验证的对话。

近似计数：匹配的 FPRAS 如何绕过精确硬度#

精确积和式是 #P 完全的，非负矩阵积和式却有 FPRAS。杰勒姆、辛克莱与维戈达在 2001 年给出马尔可夫链算法，2004 年的期刊版成为「近似计数可以战胜精确硬度」的样板。对象是二部图完美匹配，或等价地，非负矩阵的积和式。

算法不直接数。它在「近完美匹配」的状态空间上做随机游走：允许少量未匹配顶点，用边的插入、删除和轮换连接相邻状态。若链快速混合，则近似均匀抽样可得；再沿自归约的边把抽样变成计数。混合时间的界来自耦合与传导（conductance），技术核心是证明膨胀不会在「几乎完美」的层之间塌掉。早期版本对矩阵条目的比值有限制，后来的修正去掉了若干洞。对一般图的完美匹配计数，FPRAS 是否存在，在若干加权版本上仍更棘手；二部图是目前最干净的胜利。

对比决策版网络流：最大匹配的基数可以用流在多项式时间算出来，那是基数，不是个数。FPRAS 给出的是个数的相对近似，不是一张匹配。工程上若只需要「有没有完美匹配」或「最大匹配有多大」，不必走 #P；只有统计物理里的配分函数、永久式型的生成函数，才把人逼进近似计数。

另一条近似路线是相关性衰减与条形图方法，用于独立集、着色等自旋系统，当温度或度数满足条件时给出确定性 FPTAS。它们和 MCMC 是对手，也是互补：一个给混合时间，一个给递推收缩。#P 完全不意味着「随机算法也没希望」，它意味着希望必须改问题——改成近似、改成有界度、改成高温。

Holant：局部签名上的计数，而不是再写一遍 SAT#

瓦利安特在 2000 年代提出 Holant 问题：变量放在边上，顶点放局部约束函数（签名），求所有赋值的加权和。它覆盖匹配多项式、割多项式以及若干统计物理配分函数，却不强迫问题先写成约束满足的解计数。平面二聚体的 Kasteleyn 方法是前史；全息算法把「做一次可逆线性变换，使局部函数变成匹配门」写成系统手续。

Holant 的意义不是再列一张完全问题表。难度可以对齐到局部函数的代数签名：有的签名在 P，有的 #P 硬，中间还有可多项式插值的轨迹。蔡进一、陈汐等人给出布尔约束族上的计数二分法——要么多项式，要么 #P 完全。读这些定理时，重点不是背诵哪一个签名可解，而是接受：计数的易难边界可以是代数簇上的超曲面，而不是 NP 完全那条组合归约链的简单拷贝。全息算法识别的是 P 中的岛屿，不是把 #P 填平。

与 NP 的关系：判定、计数、随机#

把关系写清楚，避免以后每次都重讲。

NP 是语言类：是/否。#P 是函数类：输出一个整数。对应的语言类 PP（概率多项式，接受路径是否过半）和 $\mathrm{P}^{\#\mathrm{P}}$ 把函数转回判定。Toda 说 PH 进得了 $\mathrm{P}^{\#\mathrm{P}}$；已知 $\mathrm{P}^{\#\mathrm{P}}$ 包含 PP。NP 在下面，#P 神谕在上面，中间夹着随机与奇偶。

NP 完全问题的计数版通常 #P 完全，但「判定容易」不能推出「计数容易」，「判定困难」也不能推出「不能近似」。分类必须三项并列：判定复杂度、精确计数复杂度、近似计数复杂度。完美匹配是 (P, #P 完全, 有 FPRAS)。一般图的哈密顿回路计数更狠，连近似也往往继承决策硬度。#SAT 在近似上对某些受限公式（DNF、某些 SAT 变体）有 FPRAS，对 3-CNF 的相对近似则与 NP 硬的间隙问题相连。

随机性是第三轴。BPP 是否等于 P 未决；近似计数的 FPRAS 定义里已经内置随机。若未来 derandomize 成功，一部分 FPRAS 会变成 FPTAS。杰勒姆–瓦利安特–瓦齐拉尼的抽样–计数等价，本身就是随机归约。计数复杂度因此不是 NP 的附录，它是把判定、计数、随机、近似四张地图钉在同一块板上的钉子。

分类表可以记三行。完美匹配：判定在 P，精确计数 #P 完全，相对近似有 FPRAS。生成树：三项都在 FP，因为矩阵树定理把个数写成行列式。3-SAT：判定 NP 完全，精确计数 #P 完全，相对近似在标准假设下继承间隙硬度。同一门课里的「图问题」或「逻辑问题」不能共用一张难度标签。把计数写成 P vs NP 的复述，会丢掉这张三列地图，而这张地图才是本领域存在的理由。

代价与争议#

#P 完全被误当成停工令。编译器、约束求解、概率推理里每天都在数：模型计数（#SAT）、概率图模型的配分函数、网络可靠性。实用求解器（如 knowledge compilation、DPLL 计数、WMC）在结构化实例上可以很快，最坏情况硬度没有消失，只是被结构吃掉。把瓦利安特的定理读成「不要数」，是把最坏情况当成了平均情况。

Toda 定理的教学代价是神谕滥用。学生容易记住「#P 比 PH 强」，忘了那是一次查询加后处理，不是 #P 函数本身包含 PH 语言。函数类和语言类的类型错误，会让后面的 PP、C=P、Mod$_k$P 全部缠在一起。

近似一侧的争议更具体。MCMC 的混合时间界常常远大于实践观察到的混合；理论保证的多项式次数可以高到没有工程意义。FPRAS 存在是复杂性分类，不一定是可部署算法。反过来，没有 FPRAS 的问题，启发式温度调度有时仍然给出有用的数——只是你不再拥有相对误差的证明。统计物理与理论计算机科学在配分函数上共用对象，却常在「什么算解决」上分手：一个要相变图，一个要最坏情况多项式。

积和式与量子计算也有一条有时被吹过头的线。玻色采样把线性光学的输出分布和积和式联系起来，用于量子优势论证。那是平均情况、近似采样的硬度，不是「量子计算机在算积和式」。把 Valiant 的精确 #P 完全直接翻译成量子优势，会跳过中间所有的平均情况假设。

Holant 与全息同样容易被读成后门。能被匹配门吃掉的局部函数落在特殊代数簇上，适用范围窄。瓦利安特把全息定位为识别 P 中的岛屿：先变换，再匹配，而不是给任意 #SAT 实例开一条多项式通道。工程上若问题碰巧是平面二聚体或可全息化的签名，就走 P；否则仍要 FPRAS 或知识编译。分类先于求解器，这才是计数复杂度对实践的接口。没有这层分类，求解器跑分只会把结构实例上的快，误读成定理已被推翻。

跨域连接#

• 组合学：#P 的完整问题几乎都是计数组合对象——匹配、可满足赋值、圈覆盖、图的同态。瓦利安特的积和式定理把一张生成函数的系数问题钉成复杂度完全性，而矩阵树定理说明同类计数不必同样难。组合学提供对象与相消结构，计数复杂度提供归约；没有符号交替时，枚举的生成函数就从行列式滑向积和式。
• 线性代数：行列式是多项式时间线性代数的象征，高斯消元、特征多项式、矩阵树都走这里。积和式看起来只是去掉符号，却立刻离开线性消元能控制的空间。模 2 时两者重合，再次证明：线性代数的算法力量来自域上的加法和逆，而不是来自「看起来像求和式」。特征、模数与可否相消，决定计数走哪一边。
• 概率论：FPRAS 与近似均匀抽样的等价，把计数改写成马尔可夫链的平稳分布。混合时间、传导、耦合这些概率工具，在杰勒姆–辛克莱–维戈达的匹配算法里就是复杂度上界。隔离引理则用随机哈希把多个证据压成一个，让 NP 碰到奇偶计数。概率在这里不是应用装饰，它是连接判定类与计数类的归约语言。
• 证明：户田定理是典型的「用随机与代数改写量词交替」的证明，而不是直接给 #SAT 一个算法。阅读时必须盯住神谕的次数：一次 #P 查询与多项式层级之间的包含，是证明策略的产物，不能抄成「计数问题包含分层问题」。证明的形态——隔离、奇偶、线性组合——本身就是这个领域的内容。

参考文献#

• Valiant, L. G. "The Complexity of Computing the Permanent." Theoretical Computer Science 8(2):189–201, 1979.
• Valiant, L. G. "The Complexity of Enumeration and Reliability Problems." SIAM Journal on Computing 8(3):410–421, 1979.
• Toda, S. "PP is as Hard as the Polynomial-Time Hierarchy." SIAM Journal on Computing 20(5):865–877, 1991. （会议版 1989）对象见 户田 1991。
• Jerrum, M., Valiant, L. G. & Vazirani, V. V. "Random Generation of Combinatorial Structures from a Uniform Distribution." Theoretical Computer Science 43:169–188, 1986.
• Jerrum, M., Sinclair, A. & Vigoda, E. "A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries." Journal of the ACM 51(4):671–697, 2004.
• Valiant, L. G. & Vazirani, V. V. "NP is as Easy as Detecting Unique Solutions." Theoretical Computer Science 47:85–93, 1986.
• Valiant, L. G. "Holographic Algorithms." SIAM Journal on Computing 37(5):1565–1594, 2008.
• Cai, J.-Y. & Chen, X. Complexity Dichotomies for Counting Problems. Cambridge University Press, 2017.

延伸阅读#

• Arora, S. & Barak, B. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. 第 17 章。
• Jerrum, M. Counting, Sampling and Integrating: Algorithms and Complexity. Birkhäuser, 2003.