| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429038 | Information Processing Letters | 2011 | 6 Pages |
Abstract
Holographic reduction is a powerful tool to divide a line between tractable cases and #P-hardness. Based on dichotomies of #CSP, Holant⁎ and Holantc problem, we succeed to give a dichotomy for some particular problems in Cai et al. (2008) [5] and Valiant (2004) [8].
► We prove #P-hardness for some counting problems. ► It is motivated by the holographic algorithm proposed by Valiant. ► As a result, we establish some dichotomies for these problems.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Chen Yuan, Haibin Kan,