Progress in Complexity of Counting Problems

摘要

There has been remarkable progress in the classification program of the complexity of counting problems. This program is carried out in at least three interrelated formulations: Graph Homomorphisms, Counting CSP, and Holant Problems. In each formulation, complexity dichotomy theorems have been achieved which classify every problem in a given class to be either solvable in polynomial time or #P-hard.