Complexity Dichotomies of Counting Problems
Complexity Dichotomies of Counting Problems
复制标题
计数问题的复杂性二分法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
P. Lu
中科院分区：
文献类型：
--
作者：
P. Lu
为了研究计数问题的复杂性，人们提出了一些有趣的框架，如约束满足问题(#CSP)和图同态。最近，我们提出并探索了一个新的替代框架，称为Holant问题。它是对约束函数的改进，具有更明确的作用。图同态和#CSP都可以看作Holant问题的特殊子框架。这样的框架很有趣的一个原因是，这种语言的表现力足够强，可以表达许多自然计数问题，同时足够具体，可以证明关于其复杂性的完整分类定理，这被称为二分法定理。从Holant框架的统一角度，我们总结了计数问题的各种二分法以及所使用的证明技巧。本调查以作者在第四届国际华人数学家大会(ICCM 2010)上的演讲为材料。
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).
登录
查看更多内容
DOI：
10.1137/100811258
发表时间：
2010-03
期刊：
SIAM J. Comput.
影响因子：
--
作者：
M. Dyer;David Richerby
通讯作者：
M. Dyer;David Richerby
DOI：
10.1145/1806689.1806789
发表时间：
2010-03
期刊：
--
影响因子：
--
作者：
M. Dyer;David Richerby
通讯作者：
M. Dyer;David Richerby
非负权有向图同态的可判定二分定理
影响因子：
1.4
作者：
Cai, Jin-Yi;Chen, Xi.
通讯作者：
Chen, Xi.
DOI：
10.1137/070690201
发表时间：
2007-04
期刊：
SIAM J. Comput.
影响因子：
--
作者：
M. Dyer;L. A. Goldberg;M. Jerrum
通讯作者：
M. Dyer;L. A. Goldberg;M. Jerrum
DOI：
10.1016/j.jcss.2011.12.002
发表时间：
2010-05
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
A. Bulatov;M. Dyer;L. A. Goldberg;Markus Jalsenius;M. Jerrum;David Richerby
通讯作者：
A. Bulatov;M. Dyer;L. A. Goldberg;Markus Jalsenius;M. Jerrum;David Richerby