关于图中完美匹配枚举（Listing）与计数（counting）的疑问

嘿，这个问题戳中了很多人刚接触#P复杂度类时的困惑点，太值得聊一聊了！

首先先把Fukuda在《Polyhedral Computation》里的原话放出来：

It is known that the counting problem [of perfect matchings] is #P-complete even for bipartite graphs. There are polynomial algorithms for the listing problem.

你觉得“能高效枚举所有匹配就能高效计数”，这个逻辑乍看没问题，但核心误区在于两个问题的“高效（多项式时间）”定义完全不一样：

• 对于枚举问题来说，所谓的“多项式算法”，指的是输出每一个完美匹配的时间是多项式级的，或者说总时间是 O(N + k * poly(n))——这里的k是完美匹配的总数，n是图的规模。如果k本身是指数级的（比如某些二分图能有2^n量级的完美匹配），那枚举所有匹配的总时间还是指数级的，根本做不到“多项式时间内完成全部枚举”。
• 而计数问题的#P-complete，是说不存在一个能在多项式时间内直接算出k的算法——不管k是多大，都要求在poly(n)的时间里给出结果，这和“枚举完所有匹配再数个数”完全不是一个难度级别。

举个直观的例子：n个顶点的完全二分图K_{n,n}，它的完美匹配数是n!，这是妥妥的指数增长。枚举所有匹配的话，总时间肯定是O(n! * poly(n))，这是指数时间；但计数问题是要直接算出n!这个数，#P-complete就意味着（除非P=NP）没有任何多项式时间的算法能直接得到这个结果。

简单来说，你想的“枚举后计数”本质是用指数时间的方法解决计数问题，但#P-complete说的是不存在多项式时间的计数方法，这两者并不矛盾~

备注：内容来源于stack exchange，提问作者Greg82