形式陈述

函数 $f:\{0,1{\}}^{\ast }\to \mathbb{N}$ 属于 $\mathrm{\#}\mathbf{P}$，若存在非确定性多项式时间机器 $M$，使

$$f(x)=\mathrm{\#}\{M\text{ 在输入 }x\text{ 上的接受计算分支}\}.$$

等价地，它计数一个多项式时间可验证关系的见证数。#P 是函数类，不是语言类。

直觉

NP 只问是否至少有一个见证，#P 要求精确知道有多少见证；布尔存在性被提升为整数计数。

例子与边界

#SAT 计数满足赋值；0/1 permanent 计数二分图完美匹配。把 “#P” 解释为“多项式时间计数”是错误的；输出值本身可指数大，但二进制位数仍为多项式。

推论与应用

它连接计数问题、概率计算、partition function、Valiant permanent 定理和 Toda 定理。

参考资料

• Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach (2009), counting complexity.
• Leslie G. Valiant, The Complexity of Computing the Permanent (1979), permanent and #P-completeness.