计数复杂性类 #P

NP 只问是否至少有一个见证，#P 则输出多项式时间非确定机器的接受路径数，把布尔存在性提升为整数计数。存在性只需区分零与非零，计数则必须分辨指数范围内的精确整数，因此通常比对应 NP 判定问题承载更多信息。它是函数类，不应直接写成普通语言集合；“#P 完全”也需指定函数归约。

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

#SAT 输入布尔公式并输出满足赋值数。若能精确计算 #SAT，就可检查结果是否大于零来判定 SAT；还可逐变量固定取值，通过两次计数恢复一个满足赋值。完美匹配的存在性在 P 中，但二分图完美匹配计数同样属于重要计数问题，展示判定容易不代表精确计数容易。

非确定机器的路径编码会影响原始路径数，因此定义要求固定合理模型，完整性归约要控制计数关系。近似计数、模计数和采样与精确 #P 计算不同，不能由“估得很准”直接替代精确答案。

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

该类建立在 非确定多项式时间公理库非确定性时间复杂性类Nondeterministic time class · NTIME由非确定性图灵机在给定时间界内判定的语言集合。 与 函数公理库函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。 输出上。PP公理库复杂度类 PPPP · Probabilistic polynomial time由概率多项式时间机器以严格多数计算路径判定的语言集合。 可通过比较 #P 计数定义，多项式层级又被 Toda 定理包含在 $P^{\mathrm{\#}P}$ 中；概率计算、组合枚举和统计物理配分函数都常出现 #P 型结构。