ECCC-Report TR11-093https://eccc.weizmann.ac.il/report/2011/093Comments and Revisions published for TR11-093en-usWed, 15 Jun 2011 04:25:17 +0300
Paper TR11-093
| Complexity Dichotomies of Counting Problems |
Pinyan Lu
https://eccc.weizmann.ac.il/report/2011/093In 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).Wed, 15 Jun 2011 04:25:17 +0300https://eccc.weizmann.ac.il/report/2011/093