Valiant 1979：积和式怎样把计数写成比判定更硬的类

破除误解：积和式不是「去掉符号的行列式算法」，也不是计数总览#

第一层误解把标题听成「积和式没有算法」，或听成完美匹配不可判定。积和式有算法：把 $n!$ 个置换逐项乘起来再相加即可；莱瑟（Herbert J. Ryser）1963 年的手续把时间降到大约 $2^{n+O(\log n)}$。二部图「是否存在完美匹配」更早有多项式手续，霍尔（Philip Hall）的相异代表系、霍普克罗夫特与卡普 1973 年的匹配算法都属于判定侧。瓦利安特要给的不是停机意义上的不可能，而是一条关于计数资源的完全性：输出那个整数，其难度与数任意多项式时间非确定性机器的接受计算条数相当。把积和式听成停机问题，会把 1979 年收进 1936 年；把它听成「匹配没有算法」，会把判定与计数叠成一句话。

第二层误解把教材里后来的标准句提前写进这一年：「#P 就是 NP 的计数版，所以 SAT 难则 #SAT 难，积和式跟着难。」对 NP 完全问题，数解往往「因为显然」而完全：库克那份编译若再做成个数保持的，满足赋值的个数就是接受计算的条数。瓦利安特写明，这一档并不令人吃惊。令人吃惊的是积和式：它自然对应的是数完美匹配、数相异代表系，而这两个判定问题都在 $P$ 里。完全性因此不是从「判定已经完全」偷运过来的，而是一次算术归约把任意计数问题译进一张矩阵。把 1979 年读成「又一个 NP 完全问题的计数版」，会把本页的钉子说成库克钉子的附录。

第三层误解把「行列式能算，积和式只差正负号」听成高斯消元应当原样可用，或听成已经有人用简单的矩阵变换把积和式变成行列式。莱布尼茨展开里，行列式对每个置换乘上符号 $\mathrm{sgn}(\sigma)$，积和式把符号全部换成 $+1$。高斯消元依赖的是加法与减法可以相消；去掉符号之后，那套相消不再对应同一个函数。波利亚（George Pólya）1913 年的习题、马库斯与明克（Marvin Marcus, Henryk Minc）1961 年的关系定理，都在追问：有没有一种简单的改写，把积和式送回行列式。结果是否定的，除了后来所称的可转换矩阵一类特例。模 2 是另一类特例：$-1\equiv 1\pmod{2}$，积和式与行列式重合，因而可多项式计算。把「看起来像」听成「复杂度相同」，会把一次代数相似收成一次算法迁移。

第四层误解把对象听成 计数复杂度 整张地图，或听成 1984 年的概率近似正确学习，或听成电路上的 VP 对 VNP。那些都是后话。本页停在 1979 年的计数图灵机、神谕归约，以及 0-1 积和式的完全性。归约口径是带函数神谕的询问机，与库克 1971 年同类，不是卡普次年收紧的多一映射。本页也不把模 $2^k$ 的多项式手续写成求值代码。

计数图灵机、积和式，以及把接受条数写成矩阵#

装置从计数图灵机开始。它是标准的非确定性图灵机，另加一个辅助输出装置：输入跑完之后，装置把接受计算的条数用二进制打在一条专用带子上。时间复杂度按最长的那条接受计算来量，与普通非确定性机器相同。定义 2.2 说：$\mathrm{\#P}$ 是多项式时间计数图灵机所能计算的函数类。确定性多项式时间可计算的函数记作 $\mathrm{FP}$。瓦利安特点明，这个类与吉尔（John Gill）1974 年的多项式时间概率机器、西蒙（Janos Simon）1975 年论文里的阈值机器，在本质上相当。#P 不是语言类。它输出一个整数。问「个数是否大于零」可以把函数压回判定，但函数本身比判定多带一个计数器。

归约是神谕式的。询问机除工作带外还有询问带与回答带；进入询问状态后，神谕在单位时间内返回一个多项式有界函数的值。问题 $y$ 是 $\mathrm{\#P}$ 困难的，当且仅当 $\mathrm{\#P}\subseteq\mathrm{FP}^{y}$；若同时还满足 $y\in\mathrm{\#P}$，则称完全。这是库克口径在函数上的延伸：允许对积和式作多项式多次询问，不要求一次多一映射就把个数译过去。后来本-多尔与哈莱维（Ben-Dor, Halevi）1993 年才把 0-1 积和式收到更弱的计数归约下。1979 年的钉子钉在神谕上。把完全性听成「一张矩阵的积和式恰好等于 #SAT 的值」，会把一次询问机关系收成一次等式。

$n\times n$ 矩阵 $A$ 的积和式是

$$\mathrm{per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^{n}A_{i,\sigma(i)},$$

求和跑过 $\{1,\ldots,n\}$ 的全体置换。行列式在同一条和式上再乘 $\mathrm{sgn}(\sigma)$。若 $A$ 是 0-1 矩阵，并把行当作一部的顶点、列当作另一部的顶点，则 $\mathrm{per}(A)$ 等于二部图完美匹配的个数，也等于相异代表系的个数。另一张图论翻译：把 $A$ 看成有向图的邻接矩阵（允许自环），则积和式等于圈覆盖的加权和——每个顶点恰好属于一个有向圈，权重是圈上边权的乘积。判定「有没有圈覆盖」或「有没有完美匹配」可以走多项式手续；把权重加起来则是另一档。

主编译有三步，都是存在性手续，不是求值手册。引理 3.2 修改库克 1971 年的窗口编译：给定一台多项式时间非确定性机器 $M$ 与输入 $x$，确定性机器在多项式时间内写出一份 3-合取范式，使满足赋值的个数等于 $M$ 在 $x$ 上的接受计算条数。个数保持这一步，瓦利安特归因于对库克构造的修改，并指向鲍尔等人 1973 年关于析取范式重言式的短注，以及西蒙的论文。没有这一步，积和式只能钉住命题计数，钉不住整个 $\mathrm{\#P}$。

引理 3.1 再把合取范式公式 $F$ 写成条目取自 $\{-1,0,1,2,3\}$ 的矩阵 $f(F)$，使得

$$\mathrm{per}(f(F))=4^{t(F)}\cdot s(F),$$

其中 $s(F)$ 是满足赋值个数，$t(F)$ 是「文字出现次数的两倍减去子句数」，可在多项式时间内从 $F$ 读出。构造的几何是轨道、子句交换器与接合点。每个变元对应一条轨道：好的圈覆盖必须在整条轨道上选择同一种极性，对应 $x_k$ 或 $\neg x_k$。每个子句对应一个交换器：它允许覆盖文字的任何真子集，但不允许一个文字也不覆盖——子句必须被至少一个文字满足。接合点是大约 $4\times 4$ 的局部矩阵 $X$，只通过两个端口与外界相连。瓦利安特验证：$X$ 本身的积和式为零；只拆一个端口为零；两个端口从同一端进出为零；两个端口从两端交叉进出时积和式等于同一个非零常数 4。于是，任何在接合点上「走错」的圈覆盖对总和贡献零；只有处处交叉进出的好路径存活，每条好路径贡献 $4^{t(F)}$。好路径与满足赋值一一对应。负条目在这里不是装饰：它们负责把不一致的覆盖抵消掉。本页证明的是这份算术相消存在，并把因子写成 $4$ 的幂；它不把接合点的填表写成装配说明书，也不把负权边写成攻击步骤。

引理 3.3 处理 0-1。权重大于 1 的边被换成一块只含 0-1 的子图：原边若未被圈用到，新顶点只有一种覆盖法；原边若被用到，新顶点沿一条链被覆盖，并额外乘上恰好等于原权重的若干种自环选择。于是 $\mathrm{per}(A)=\mathrm{per}(h(A))$，且 $h(A)$ 是 0-1 矩阵。任意 $\mathrm{\#P}$ 函数因此可以借助神谕询问 0-1 积和式来计算：先写成 3-CNF，再写成小整数矩阵，再写成 0-1 矩阵，最后把读到的积和式除掉已知的 $4$ 的幂。定理 1 的精确句是：计算 $n\times n$ 的 0-1 积和式是 NP 困难的，并且（在多项式因子内）至少与数任意非确定性多项式时间机器的接受计算一样难；用定义 2.2 的语言，它是 $\mathrm{\#P}$ 完全的。

模运算把同一函数涂上不同颜色。定理 2：对任何不是 2 的幂的整数 $K$，0-1 积和式模 $K$ 是 $\mathrm{UP}$ 困难的。$\mathrm{UP}$ 是至多一条接受计算的非确定性多项式时间类；若 $P=\mathrm{UP}$，则对单值函数而言，「核对」与「求值」多项式等价。瓦利安特把模 3 写得更刺耳：若积和式模 3 可多项式计算，则迪菲与赫尔曼 1976 年所设想的那类方案将不存在。这是一条条件句，不是一份密码分析步骤。定理 3 是论文里少有的正面算法：整数矩阵的积和式模 $2^k$，当 $k\ge 2$ 时可在 $O(n^{4k-3})$ 步内算完；$k=1$ 时积和式等于行列式，高斯消元给出 $O(n^{3})$，施特拉森 1969 年的矩阵乘法把它降到 $O(n^{2.81})$。证明把高斯消元改写成「加一行到另一行」在积和式上的加法恒等式，并在模 $2^k$ 下控制 2 的因子。模 2 的幂因此是多项式岛屿；奇数模则回到困难。同一函数，模掉多少，颜色可以翻转。

论文末节标明计数类不是单层的 $\mathrm{\#P}$：模 $K$ 算术、无标记子图计数、以及把变元分成存在与见证两半的 NSAT，各落在不同档上。那些句子不是本页的主编译。

它证明了什么，没有覆盖什么#

它证明了：0-1 矩阵的积和式对 $\mathrm{\#P}$ 完全。任意多项式时间非确定性机器的接受条数，都可以经神谕归约交给这个函数。二部图完美匹配的个数因此完全——尽管对应的判定属于 $P$。它还证明：模一个不是 2 的幂的整数时，0-1 积和式对 $\mathrm{UP}$ 困难；模 $2^k$ 时存在多项式时间手续，次数随 $k$ 升高。用后来的话说，这就是「判定容易并不蕴含计数容易」的第一枚代数钉子。生成树个数仍可走基尔霍夫矩阵树定理，那是行列式一侧的幸运，不是对本页的反驳。

它没有证明积和式不能在确定性多项式时间内计算。完全性是条件句：若 0-1 积和式属于 $\mathrm{FP}$，则 $\mathrm{\#P}\subseteq\mathrm{FP}$，进而 $P=NP$。分离本身仍开放。它也没有采用多一归约作为定义。卡普 1972 年把判定问题收紧为一次实例映射；瓦利安特把计数问题写成对函数神谕的多项式询问。主编译里公式到矩阵那一步其实给出显式因子 $4^{t(F)}$，看起来像一次计数归约；定义上的钉子仍钉在 $\mathrm{FP}^{y}$。把 1979 年读成卡普口径，会把一次询问机收成一次等式。

它没有覆盖 户田 1991 的定理，没有覆盖杰勒姆–瓦利安特–瓦齐拉尼 1986 年的抽样与近似计数等价，没有覆盖杰勒姆–辛克莱–维戈达后来对非负积和式的 FPRAS，也没有覆盖算术电路里 VP 对 VNP 的那条前线。那些属于 计数复杂度 与 电路复杂度 的地图，不是这十三页的对象。1984 年的 PAC 学习是另一篇论文。概率可验证明不在这里打开。姊妹篇 SIAM 8(3) 把网络可靠性、极大团计数、$s$-$t$ 简单路计数等钉进同一类，本页只借用它来标明「更多完全问题在下一篇」。

稳健性来自算术相消，不来自后来的求解器。只要圈覆盖的权重能被局部接合点过滤，新的计数问题就可以先译成有向图，再译成 0-1 矩阵；多项式次数会变，完全性这一档不会变。工业上的模型计数能解开许多带结构的实例，并不把最坏情况的钉子作废。概念证据到此为止。计数图灵机回答的是「#P 在 1979 年用哪一种机器写下」；积和式回答的是「一个判定属于 $P$ 的组合函数，其精确值仍可完全」。两句都不是操作单。

跨域连接#

• 计数复杂度：总览页把 $\mathrm{\#P}$、户田定理、FPRAS 与 Holant 收成一张学科地图；本页只提供地图上的第一枚钉子。钉子的形状是 0-1 积和式在神谕归约下的完全性，不是后来的近似抽样，也不是平面二聚体的多项式岛屿。把两页叠在一起读，才能看见：计数类先作为「数接受计算」出现，再被铺成近似、随机与签名二分。地图可以后写；钉子的金属成分以 1979 年的定义为准。
• 计算复杂性：总览把 $P$、$NP$ 与完全性画成判定地图。本页在同一张纸的另一侧写下函数类：输出不再是是或否，而是一个整数。若这个整数可多项式算出，判定地图上的 $NP$ 也会塌进 $P$。把计数听成「更细的 NP」，会把函数类收成语言类。萨维奇的平方模拟回答空间；库克与卡普回答判定完全性；本页回答计数完全性。三句话共用图灵机，资源账本不同。
• 库克一九七一年论文：那八页把「存在接受计算」编译成可满足公式；本页的引理 3.2 要求同一份编译保持个数。库克问有没有，瓦利安特问有多少，并且要这个「多少」再被积和式乘上一个容易除掉的 $4$ 的幂。询问机在两页里都合法：库克用它翻转重言式的极性，瓦利安特用它询问一个函数值。把积和式听成 SAT 判定，会把计数钉子收成 1971 年的存在性钉子。
• 卡普一九七二年论文：二十一题全是判定。积和式对应的判定——有没有完美匹配——并不在那张图上，它属于 $P$。卡普回答「哪些判定与 SAT 同生共死」；本页回答「一个已经属于 $P$ 的判定，其计数版本仍可完全」。多一箭头解释不了这件事，因为两边的是非题已经分家，分家之后仍能用算术把个数译进矩阵。把二十一题听成积和式的应用清单，会把函数完全性收成组合判定。
• 可计算性：停机问题把「有没有手续」写成不可判定。本页假定手续存在：枚举置换、枚举匹配、枚举赋值都停得下来。问的是手续能否被多项式时钟替代，以及输出能否从是非换成计数。可判定、多项式可判定、多项式可计数，是三层边界。把积和式听成不可计算，会把资源问题收成存在问题。对角化在无界时间里分开递归与递归可枚举；带多项式时钟之后，瓦利安特表明：连「判定已经容易」也不能把计数从完全档里救出来。
• 证明：积和式的莱布尼茨和是一条关于全体置换的普遍等式；#P 完全性并不去核验这条等式的每一项。它证明存在一份多项式书写手续，把任意计数机器的接受条数译成一张矩阵的积和式，只差一个已知因子。证书是归约，不是把 $n!$ 项列在纸上。数学里的普遍证明要求从公理推出必然；这里的必然相对于计数图灵机的转移表。接合点上的负权负责把坏路径抵消，这种相消是证明策略，不是把矩阵交给求解器之前的预处理步骤。把完全性听成已经给出积和式的闭式算法，会把翻译手续说成求值手续。

参考文献#

• L. G. Valiant, "The Complexity of Computing the Permanent", Theoretical Computer Science 8(2), 1979, pp. 189–201. DOI: 10.1016/0304-3975(79)90044-6. —— 本文对象：计数图灵机与 $\mathrm{\#P}$、0-1 积和式的完全性，以及模 $2^k$ 的多项式手续。
• L. G. Valiant, "The Complexity of Enumeration and Reliability Problems", SIAM Journal on Computing 8(3), 1979, pp. 410–421. DOI: 10.1137/0208032. —— 同年姊妹篇，用以标明更多完全问题不是本页封面。
• Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971, pp. 151–158. DOI: 10.1145/800157.805047. —— 引理 3.2 所修改的窗口编译。
• Richard M. Karp, "Reducibility among Combinatorial Problems", in Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103. —— 判定侧的多一口径，用以标明本页钉的是函数神谕。
• J. E. Hopcroft & R. M. Karp, "An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs", SIAM Journal on Computing 2(4), 1973, pp. 225–231. DOI: 10.1137/0202019. —— 论文用来对照「检测匹配在 $P$」的手续。
• H. J. Ryser, Combinatorial Mathematics, Carus Mathematical Monographs no. 14, Mathematical Association of America, 1963. —— 论文所引的指数时间积和式手续。
• Marvin Marcus & Henryk Minc, "On the Relation Between the Determinant and the Permanent", Illinois Journal of Mathematics 5(3), 1961, pp. 376–381. DOI: 10.1215/ijm/1255630880. —— 论文用来标明「简单变换送回行列式」的否定结果。
• John Gill, "Computational Complexity of Probabilistic Turing Machines", Proceedings of the 6th Annual ACM Symposium on Theory of Computing, 1974, pp. 91–95. DOI: 10.1145/800119.803889. —— 论文点名与 $\mathrm{\#P}$ 本质相当的概率机器。

延伸阅读#

• 与 计数复杂度 对读：先看 1979 年的钉子，再看户田、FPRAS 与 Holant 如何把地图铺开。
• 与 计算复杂性 对读：判定类与函数类必须分开写，才能看见「匹配容易、计数完全」不是自相矛盾。
• 与 库克一九七一年论文 对读：存在性编译如何被改成个数保持，是两页之间的那一条缝。
• 与 卡普一九七二年论文 对读：二十一题里没有「完美匹配判定」，正因为那一档已经属于 $P$。
• 与 可计算性 对读：可判定并不给出多项式可计数。
• 与 电路复杂度 对读：VP 对 VNP 把行列式与积和式再写一遍，对象是算术电路，不是 1979 年的计数图灵机。