计数复杂度类 #P

#P读作sharp-P,是由瓦利安特于一九七九年引入的计数复杂度类。它包含这样一类函数:给定一个NP型判定问题,不再问是否存在解,而是精确统计接受路径或可行解的数量。它把判定问题提升为计数问题。

概述

形式上,#P中的函数计算某个多项式时间非确定图灵机在给定输入上接受路径的条数。许多问题的判定版本在NP中,而其计数版本落在#P中,后者通常严格更难,因为知道有解并不意味着能数清解的总数。

核心原理

• 每个#P函数对应一台非确定多项式时间机器,函数值等于其接受计算路径的数目。
• #P完全问题是该类中最难的,任何#P问题都能高效归约到它。
• 计算矩阵永久式是经典的#P完全问题,尽管对应的行列式却能多项式时间计算。
• 统计布尔公式满足赋值个数的问题,即#SAT,也是#P完全的。

应用场景

#P刻画了大量涉及计数和概率的计算难度。它与统计物理中的配分函数、图论中的完美匹配计数、可靠性网络分析以及概率推断密切相关。托达定理进一步表明,整个多项式层级都能用#P的一次询问解决,凸显了计数能力的强大,这也解释了为何近似计数和随机采样成为处理这些难题的主要途径。

常见问题

问:#P比NP更难吗?答:一般认为是。判定一个问题是否有解至多和数出解的个数一样难,而托达定理显示#P能覆盖整个多项式层级,普遍相信#P严格难于NP。

问:为什么永久式难而行列式容易?答:两者公式几乎相同,只差符号项。行列式的交错符号允许高斯消元等抵消技巧从而多项式可算,而永久式全为正项无法抵消,导致其成为#P完全的困难问题。