随机近似计数

直接从全部 $2^n$ 个赋值中抽样，会把大量时间花在不满足公式的点上。例如只有一个包含全部变量的项时，命中的概率是 $2^{-n}$。DNF 额外提供了一张“容易生成局部成功样本”的清单：每个自洽项的大小已知，在项内均匀抽样也很容易。算法利用这张清单，把抽样空间移到已知能满足某个项的赋值上。[3]

这样做产生的代价是重复覆盖。一个赋值若同时满足三个项，就在 $\mathrm{\Omega }$ 中出现三次；直接报告 $S$ 会把它计数三次。给每份副本保留项标签后，算法能够指定其中一份为代表，把另外两份记为零。它不必实际列出并集，只须检查抽到的赋值是否还满足更早的项。

均匀性与无偏性。 对任意 $(i,x)\in \mathrm{\Omega }$，两阶段抽样给出

因此均匀的是带标签副本，而不是去重后的满足赋值。每个满足赋值恰有一个代表，故 $\mathrm{\Omega }$ 的 $S$ 个元素中恰有 $C$ 个使 $B=1$。令 $p=\text{Pr}[B=1]$，则

这里使用期望公理库期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分，概括加权平均与总体质量平衡。的线性性。无偏只保证重复运行的平均值正确；一次运行要有相对误差保证，还必须控制样本均值偏离 $p$ 的概率。

代表不会太稀少。 每个 $A_i$ 都包含于满足赋值并集，所以 $a_i\le C$，从而

这个下界是效率的关键。$C/2^n$ 可以指数小，但 $C/S$ 最多因 $m$ 份重复覆盖而下降，不会比 $1/m$ 更小。算法因此能在不知道答案 $C$ 的情况下预先选择足够的样本数。

从集中界到相对误差。 令 $Z=\sum _{t=1}^N{B}_t$。独立抽样使 $B_t$ 成为独立同分布的 Bernoulli 随机变量；对 $0<\epsilon \le 1$，乘法形式的 Chernoff 界公理库Chernoff 方法与 Chernoff 界Chernoff method · Chernoff bounds从指数矩与 Markov 不等式推导尾界，给出独立 Bernoulli 和的乘法形式、KL 形式及适用条件。给出

因为 $C=Sp>0$，事件 $|\hat{C}-C|>\epsilon C$ 与 $|Z-Np|>\epsilon Np$ 完全相同。取上述 $N$ 便使右端不超过 $\delta$，得到所需保证。这一步同时解释了平方精度代价 ${\epsilon }^{-2}$ 与对数置信代价 $\log \left(1/\delta \right)$；仅有大数定律还不能给出这样的有限样本界。

取三个变量上的公式

这里 $A_1=\{110,111\}$，$A_2=\{011,111\}$，所以 $a_1=a_2=2$、$S=4$，而去重后 $C=3$。两项各以 $1/2$ 的概率选中，项内两种赋值也各以 $1/2$ 的概率生成。四个带标签样本恰好等概率：

单轮缩放输出 $Y=4B$ 以 $3/4$ 的概率取 $4$，以 $1/4$ 的概率取 $0$，因此 $\mathbb{E}Y=3$、$\mathrm{Var}(Y)=16(3/4)(1/4)=3$。$N$ 轮均值的方差为 $3/N$。原赋值空间中的满足率是 $3/8$，新空间中的代表比例是 $3/4$；两种概率回答不同问题，不能互相替换。

若 $\epsilon =0.2$、$\delta =0.05$，理想抽样的通用界给出 $N=554$。这保证的是多次独立运行中至少 $95\mathrm{\%}$ 的输出落在 $[2.4,3.6]$，并不要求输出为整数，也不声称 $554$ 是此实例的最少样本数。

更极端地，若 $F=x_1\wedge \cdots \wedge x_n$，直接赋值抽样的成功率仅为 $2^{-n}$；覆盖空间却只有一个元素，$S=C=1$，$B$ 恒为 $1$，一轮即得到精确答案。相反，将同一个自洽项重复 $m$ 次，会得到 $p=1/m$，说明证明中的最坏下界确实能达到。删除重复整项可以改善这种输入，却不是正确性所需步骤。

空合取项覆盖全部 $2^n$ 个赋值，公式此时为真；算法仍然适用，也可以直接输出 $2^n$。空析取或只含矛盾项的公式则必须走精确零分支：当 $C=0$ 时，相对误差区间退化为 $\{0\}$，不能除以 $C$，更不能用“绝对误差很小”替代精确零。

公平随机位下的抽样实现。 预先计算整数前缀和 $s_i=\sum _{j\le i}{a}_j$。若能均匀生成整数 $u\in \{0,\dots ,S-1\}$，就选择唯一满足 $s_{i-1}\le u<s_i$ 的项。这段整数区间恰有 $a_i$ 个元素，因此精确实现 $a_i/S$ 的权重，无需浮点概率。

当 $S>1$ 时，令 $q=\lceil {\log }_{2}S\rceil$，用 $q$ 个新公平随机位生成 $r\in \{0,\dots ,2^q-1\}$；若 $r<S$ 就接受为 $u$，否则重试。一次接受率 $S/2^q>1/2$，且每个可接受整数的概率相同，故接受结果严格均匀。$S=1$ 时直接令 $u=0$。无限重试的平均次数小于 $2$，但它没有有限的最坏运行时间上界。

截断与失败预算。 要使每条随机执行都按时结束，改用

每轮整数抽样最多尝试 $R$ 次；若仍未接受，就停止整个算法并返回 $0$，把这种情况计入失败。在刚才的数值例子中，这给出 $N=658$、$R=15$。其中 $S=4$ 恰为二的幂，实际上每次尝试都会接受；$R$ 是统一覆盖一般输入的预算。

证明时，为每轮预先安排相互独立的无限随机带，将截断算法与使用同一批随机带、无限重试的理想算法耦合。某轮前 $R$ 次全被拒绝的概率至多 $2^{-R}$，故至少一轮触发截断的概率至多 $N{2}^{-R}\le \delta /2$。没有截断时，两种算法的所有样本与输出逐项相同；理想算法的集中失败概率由新的 $N$ 控制在 $\delta /2$。因此截断算法的失败事件包含于“发生截断”与“理想估计失败”的并集，总概率至多 $\delta$。证明不需要、也没有断言截断后的无条件样本仍然独立同分布。

比特成本。 设规范化后总文字数为 $L$，令 $b=n+\lceil {\log }_2(m+1)\rceil +1$；$S$ 和各前缀和都可用 $O(b)$ 位存储。使用变量编号数组或排序可在输入长度的多项式时间内规范化，随后计算大小与前缀和花费 $O(mb)$ 位操作。每轮至多 $R$ 次生成和比较 $q\le b$ 位整数，以前缀和二分定位项花费 $O(b\log (m+1))$ 位操作；填入赋值并检查更早各项，在通常索引访问模型下花费 $O(n+L)$ 次基本操作。

为避免把机器字操作当成免费比特运算，可以保守地把整段单轮处理写成 $\mathrm{poly}(n+L+b)$ 位操作，再加 $O(Rb)$ 的拒绝预算。循环总成本由 $N$ 倍该式控制，累计 $Z$ 与输出有理数 $SZ/N$ 的整数运算只需关于 $b+\log N$ 的多项式成本。$N$ 关于 $m,1/\epsilon ,\log \left(1/\delta \right)$ 为多项式，$R=O(\log N+\log \left(1/\delta \right))$，所以得到严格的最坏多项式时间保证。实现中可用可计算的向上有理界选择 $N,R$，无须假定对数能够以无限精度免费求值。

DNF 计数展示了精确计数与近似计数公理库计数复杂性类 #PSharp-P · #P可高效验证的见证计数类；由前缀计数构造均匀生成器，并给出近似计数到近均匀采样的完整误差预算。之间的边界：容易检查单个见证，不代表容易精确求出总数；精确问题的困难性也不自动排除高概率相对近似。这里的成功依赖显式给出的覆盖、每块已知的大小和可执行的均匀抽样；将任意布尔公式先展开为 DNF 可能产生指数多个项，因而不能据此推出一般 #SAT 的 FPRAS。

FPRAS 的“完全多项式”还与PTAS、FPTAS公理库多项式时间近似方案Polynomial-time approximation scheme · PTAS对每个固定 ε>0 都在多项式时间内给出 1±ε 近似的算法族。中的参数要求相呼应，但这里额外规定了失败概率。降低 $\delta$ 通过增加独立样本实现，属于概率放大公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。的一种用途；数值估计应聚合为均值或采用另有证明的中位数方案，不能把不同数值直接当作判定答案进行多数投票。本页证明的是基本覆盖估计器，不将它的时间界混同于原论文进一步提出的自调整算法。