计数复杂性类 #P

从“有没有”走向“有多少” ​

给一个布尔公式，问“是否存在使它为真的赋值”，只需回答是或否；问“共有多少个这样的赋值”，则要返回一个整数。前者是判定问题，后者是计数问题。#P 刻画能够在多项式时间内验证的见证，其数量有多大，读作 sharp P。

例如，公式 $\phi =(x\vee y)\wedge (\mathrm{\neg }x\vee z)$ 的满足赋值数是 $4$：当 $x=0$ 时，必须 $y=1$，而 $z$ 任意；当 $x=1$ 时，必须 $z=1$，而 $y$ 任意。两种情况各贡献 $2$ 个赋值。判定算法只需找到其中一个，计数算法必须正确合并全部情况，既不遗漏，也不重复。

两个典型对象：赋值与匹配 ​

#SAT 输入一个布尔公式，输出满足赋值数。见证就是对所有变量的完整赋值，验证器把赋值代入公式。变量集合必须明确：额外加入一个未被约束的新变量，会让满足赋值数翻倍，却不改变原公式是否可满足。这展示了计数问题对编码细节的敏感性。

另一个例子是 $0$–$1$ 矩阵 $A$ 的 permanent：

把矩阵看作一个二分图的邻接矩阵。置换 $\sigma$ 为每个左侧顶点指定不同的右侧顶点；乘积为 $1$ 恰好表示这些边都存在。因此 permanent 数的是完美匹配。

取

可行的列选择只有 $(1,3,2)$ 和 $(2,1,3)$，所以 $\mathrm{perm}(A)=2$。它与行列式的外形相似，但没有置换符号带来的正负抵消；不能把行列式的高斯消元算法直接套到这里。

二分图是否有完美匹配可在多项式时间内判断，而精确计算其数量是 #P 完全问题。这比“找到一个解后继续找”更能说明计数与判定的差别：存在性很容易，也不代表总数很容易。[1][2]

完全性必须附带归约类型 ​

#SAT 在保计数归约下是 #P 完全的。这类归约构造实例 $g(x)$，并精确保留答案：$f(x)=\mathrm{\#}\mathrm{SAT}(g(x))$。它要求原见证与新见证之间存在不会增减数量的对应，单纯保留“有解当且仅当有解”不够。

对于 $0$–$1$ permanent，本条采用多项式时间 Turing 归约的完全性陈述：允许算法多次调用 permanent 计数 oracle，并进行多项式时间的额外计算。不能把它自动改写成从 #SAT 出发的保计数归约；若存在后一种归约，结合完美匹配存在性的多项式算法，就会得到 SAT 的多项式判定算法。[1][2]

这一点也影响“#P-hard”的理解：需要说明精确计算还是近似计算、允许哪种归约。精确计数的困难性结论，不会自动变成某个误差标准下的近似困难性结论。

显式 DNF 的满足赋值计数提供了具体的近似边界：覆盖抽样算法公理库DNF 计数的覆盖抽样算法DNF approximate counting · Karp–Luby coverage algorithm在带项标签的样本空间中均匀抽样，为每个满足赋值保留唯一代表，从而在严格多项式时间内以高概率近似 DNF 的满足赋值数。利用每个合取项易于计数和抽样的结构，给出 FPRAS，在关于输入长度、逆精度和对数逆失败概率的多项式时间内得到相对近似。这个结论依赖输入已经是显式 DNF；任意公式转换为 DNF 可能指数膨胀，因此它不自动推广到一般 #SAT。

计数怎样连接概率与判定 ​

若从 $\{0,1{\}}^{p(|x|)}$ 均匀抽取见证，则

于是精确计数等价于求出这个实验的精确接受概率。NP 判断接受路径是否存在；PP公理库复杂度类 PPPP · Probabilistic polynomial time由概率多项式时间机器以严格多数计算路径判定的语言集合。 的典型描述判断接受路径是否超过全部路径的一半。不同复杂性类在这里对应对同一组路径提出的不同问题。

如果所有 #P 函数都能在确定性多项式时间内精确计算，那么检查计数是否为零就能解决所有 NP 问题，因而 $\mathrm{P}=\mathrm{NP}$。反向推理却不能靠“找到一个见证后逐个删除”完成：见证可能有指数多个。

Toda 定理进一步给出 $\mathrm{PH}\subseteq {\mathrm{P}}^{\mathrm{\#}\mathrm{P}}$：多项式层级中的判定问题，可以由拥有精确计数 oracle 的多项式时间机器解决。这是计数能力的结构性结论；它并不表示普通计算机已经拥有这样的高效 oracle。[1]

精确计数怎样给出逐位均匀采样 ​

先查询 $C_x(\lambda )$。若为零，返回表示空集的符号 $\mathrm{\perp }$；否则从 $u=\lambda$ 开始，每一步按

选择下一位并令 $u\leftarrow ub$。计数为零的孩子不会被选中，所以沿途分母始终为正。对任意完整见证 $y=y_1\cdots y_m\in W_x$，路径概率望远镜相消：

这同时证明输出总是见证且在所有见证间均匀。查询数至多 $2m+1$，计数的二进制长度至多 $m+1$；指数多的见证没有被显式列出来。$m=0$ 时只需验证唯一候选空串。

三个见证的全部前缀 ​

取

变量次序为 $x,y,z$，满足赋值为 $001,010,111$。全部前缀计数为：

两条左支路径的概率分别为 $\frac{2}{3}\cdot \frac{1}{2}\cdot 1=\frac{1}{3}$；右支到 $111$ 的概率为 $\frac{1}{3}\cdot 1\cdot 1=\frac{1}{3}$。如果每次只在“有解”的两个孩子间等概率选取，根处会给右边唯一见证概率 $1/2$，左边两个各 $1/4$，并不均匀。存在性查询不足以决定正确的分支比例。

公平随机位的运行时间也要计算 ​

给定整数 $0\le A\le D$、$D\ge 1$，实现概率 $A/D$ 的分支：若 $D=1$ 直接决定；否则取 $L=\lceil {\log }_{2}D\rceil$ 个公平随机位，得到 $r\in \{0,\dots ,2^L-1\}$。若 $r\ge D$ 则重抽，否则按 $r<A$ 决定是否选第一支。接受后的 $r$ 在 $[0,D)$ 上均匀，每次接受概率大于 $1/2$，所以期望尝试数小于2。

因此，若精确延伸计数可在多项式时间完成，前面的逐位算法具有期望多项式运行时间，但重抽次数没有确定上界。这个区别不能抹去：有固定随机位数上限、总会返回见证的算法，其各输出概率都是二进有理数，无法把三个见证都赋概率 $1/3$。[3, §2]

若要求有限最坏运行时间并允许失败，还可先只抽一个均匀序号 $r\in [0,C_x(\lambda ))$，把拒绝尝试限制为 $K$ 次，耗尽则返回 $\mathrm{\perp }$。成功后按字典序反排名：在前缀 $u$ 处计算 $c_0=C_x(u0)$，若 $r<c_0$ 则走0；否则走1并把 $r$ 减去 $c_0$。不变量是 $r$ 为当前子树中的序号，最终与见证一一对应。由于唯一一次截断对各被接受序号完全对称，条件于成功时仍精确均匀，失败概率至多 $2^{-K}$。若把逐位抽样分别截断，各路径的存活概率可能不同，就不能直接作同样的条件均匀断言。

近似计数到近均匀：三个误差来源各留一份预算 ​

现在只假设前缀计数有FPRAS式的估计器公理库DNF 计数的覆盖抽样算法DNF approximate counting · Karp–Luby coverage algorithm在带项标签的样本空间中均匀抽样，为每个满足赋值保留唯一代表，从而在严格多项式时间内以高概率近似 DNF 的满足赋值数。。对每个固定查询前缀 $v$，它在确定的多项式时间内返回非负、具有多项式位长的有理数，满足

运行时间关于完整查询编码长度（含精度参数）、$1/\epsilon$、$\log \left(1/\delta \right)$ 为多项式，每次调用使用独立于既往记录的新随机位。零计数也包含在保证内：成功的相对近似必须准确返回零。

对非空 $W_x$、$m\ge 1$ 和有理目标精度 $0<\eta <1$，记所给分子、分母的二进制编码总长度为 $L_{\eta }$，设

每位分别查询 $\hat{a}={\hat{C}}_x(u0)$ 与 $\hat{b}={\hat{C}}_x(u1)$；若两者之和为零则返回 $\mathrm{\perp }$，否则以 $q=\hat{a}/(\hat{a}+\hat{b})$ 的概率选0。两个有理数通分后，$q=A/D$ 的整数分子分母仍只有多项式位数，可以精确运算；按上一节抽样，每次分支至多尝试 $K$ 轮，耗尽则返回 $\mathrm{\perp }$。最后再验证完整输出满足 $R(x,y)=1$，否则也返回 $\mathrm{\perp }$。

这个有界时间算法的输出分布 $P$ 定义在 $W_x\cup \{\mathrm{\perp }\}$ 上。令 $U_{W_x}$ 为见证均匀分布，并给 $\mathrm{\perp }$ 质量零，则

特别地，失败概率至多 $\eta$。这是总变差距离公理库总变差距离Total variation distance · TV distance两个概率分布对最优可测事件所赋概率之差的最大值。的保证，并不把失败输出删掉后才衡量误差。

自适应查询的耦合证明 ​

不能把实际算法条件化在“所有计数都估准”上，再假定抽样分布未变；这个事件可能随选中的前缀而变化。改用三个过程比较。

先定义一个仅用于证明的修正过程：某次估计若落在真计数的相对误差区间外，就用真计数替换它；分支抽样暂不截断。实际算法不知道真计数，无法执行这一修正。修正过程的每个计数都在正确区间内，正前缀也只会走向正前缀。

固定其中一步的真计数 $a,b$，记 $p=a/(a+b)$。若二者均正，写 $\hat{a}=a(1+e_0)$、$\hat{b}=b(1+e_1)$，其中 $|e_i|\le \epsilon <1/2$，则

若一个孩子计数为零，修正后的估计也为零，故 $q=p$。这个界对每一对实际取得的正确估计都成立，平均后仍成立。用共同均匀随机数耦合公理库耦合法Coupling method · Probability coupling在共同概率空间中构造具有指定边缘的随机变量，并用它们相遇的概率比较分布。两枚Bernoulli分支，使它们在当前前缀相同时以至多 $\epsilon$ 的概率走向不同孩子。直到首次分离为止逐步耦合，$m$ 步给出修正过程与精确均匀过程的总变差至多 $m\epsilon$。

其次，把真实的未截断过程与修正过程使用相同随机位运行，直到第一次需修正的计数答案。前缀虽然自适应选择，但给定每次调用前的全部记录，查询已经固定、新随机位尚未使用，故这次估计失败的条件概率仍至多 $\delta$。对至多 $2m$ 次查询使用并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，给出两过程不同的概率至多 $2m\delta$，不需要这些失败事件彼此独立。

最后比较真实过程的截断与未截断版本。给定任何一轮的正整数分母，每次尝试都以至少 $1/2$ 的概率成功，所以一次分支耗尽 $K$ 轮的条件概率至多 $2^{-K}$。至多 $m$ 次分支使截断的代价至多 $m{2}^{-K}$。最终验证是对输出施加同一确定性映射，不会增大总变差。三角不等式合并为

例如前面的三个见证、$\eta =0.1$，可取 $\epsilon =1/90$、$\delta =1/180$、$K=7$；三项界依次为 $1/30,1/30,3/128$，总和 $173/1920\approx 0.090104<0.1$。这些是保守的全局界，不声称本小例实际误差恰好等于它们。

得到了什么，没有默认得到什么 ​

查询数为 $2m$，各次精度取 $\mathrm{\Theta }(\eta /m)$，所以这个直接构造的运行时间是 $\mathrm{poly}(|x|,L_{\eta },1/\eta )$，包括读取任意给定精度编码的成本。Jerrum–Valiant–Vazirani在自约化条件下证明了更强的计数／生成等价，其生成器对精度的依赖为 $\mathrm{poly}(|x|,\log \left(1/\eta \right))$，并使用不同的逐点概率与失败约定；本页的简单分支算法没有证明那个更强结论。[3, §6]

DNF对前缀赋值后的限制仍可表示为多项式大小的显式DNF，并保留剩余变量全集，故其已有FPRAS可接入此处，得到相应的近均匀满足赋值采样。一般CNF的前缀自约化同样容易，但本页没有给出它的FPRAS。结构上的自约化、可调用的计数器和误差保证是三个分别需要落实的条件。

Toda 定理的完整归约链公理库Toda 定理Toda's theorem · PH in P with a counting oracle用哈希隔离消去固定层量词，再把奇偶计数提升到高次二的模数，完整推出 PH 包含于带精确计数 oracle 的多项式时间。进一步给出仿射隔离、固定量词层的误差预算，以及三次多项式的模提升。它用两个精确 #P 值恢复接受随机种子的整数数量，说明近似计数和普通存在性查询为何不能直接替代这个接口。

算术电路与 VP/VNP公理库算术电路与 VP/VNPArithmetic circuit · VP and VNP · 算术电路固定域上的形式多项式电路、VP/VNP 与保值投影，包含 permanent 的显式见证求和和代数成本边界。使用 permanent 的同一表达式研究另一种模型：固定域上的非一致多项式族。该页展开布尔矩阵见证的加权求和与保值投影，并区分域特征、整数计数以及两种归约接口。