Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-093 | 8th June 2011 05:47

Complexity Dichotomies of Counting Problems


Authors: Pinyan Lu
Publication: 15th June 2011 04:25
Downloads: 2507


In order to study the complexity of counting problems, several interesting frameworks have been proposed, such as Constraint Satisfaction Problems (#CSP) and Graph Homomorphisms. Recently, we proposed and explored a novel alternative framework, called Holant Problems. It is a refinement with a more explicit role for constraint functions. Both graph homomorphism and #CSP can be viewed as special sub-frameworks of Holant Problems. One reason such frameworks are interesting is because the language is expressive enough so that they can express many natural counting problems, while specific enough so that it is possible to prove complete classification theorems on their complexity, which are called dichotomy theorems. From the unified prospective of a Holant framework, we summarize various dichotomies obtained for counting problems and also proof techniques used. This survey presents material from the talk given by the author at the 4-th International Congress of Chinese Mathematicians (ICCM 2010).

ISSN 1433-8092 | Imprint