A Complexity Dichotomy for Partition Functions with Mixed Signs
A Complexity Dichotomy for Partition Functions with Mixed Signs
复制标题
混合符号配分函数的复杂度二分法
DOI：
10.1137/090757496
复制
发表时间：
2010
影响因子：
1.6
通讯作者：
Goldberg L
中科院分区：
文献类型：
--
作者：
Goldberg L
配分函数（英语：Partition functions），也称为灰态函数，形成了一个丰富的图形不变量家族，其中包含组合不变量，如k-着色数或图形的独立集数，以及统计物理学的某些“自旋玻璃”模型（如伊辛模型）的配分函数。基于Dyer和格林希尔的早期工作[Random Structures Algorithms，17（2000），pp. 260-289]和Bulatov和Grohe [理论计算。科学，348（2005），pp. 148-186]，我们完全分类的计算复杂性的分区函数。我们的主要结果是一个二分法定理，说明每个配分函数要么在多项式时间内可计算，要么是P-完全的。用真实的元素的对称矩阵来描述配分函数，并证明了给定的配分函数是多项式时间的还是#P-完全的，都是多项式时间可判定的.虽然在一般情况下，这是非常复杂的，以明确的代数或组合描述的听话的情况下，为分割功能所描述的阿达玛矩阵（这些原来是中央在我们的证明），我们得到一个简单的代数听话的标准，这说，听话的情况下，是那些“表示”的二次多项式在外地。
Partition functions, also known ashomomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number ofk-colorings or the number of independent sets of a graph and also the partition functions of certain “spin glass” models of statistical physics such as the Ising model. Building on earlier work by Dyer and Greenhill [Random Structures Algorithms, 17 (2000), pp. 260–289] and Bulatov and Grohe [Theoret. Comput. Sci., 348 (2005), pp. 148–186], we completely classify the computational complexity of partition functions. Our main result is a dichotomy theorem stating that every partition function is either computable in polynomial time or #P-complete. Partition functions are described by symmetric matrices with real entries, and we prove that it is decidable in polynomial time in terms of the matrix whether a given partition function is in polynomial time or #P-complete. While in general it is very complicated to give an explicit algebraic or combinatorial description of the tractable cases, for partition functions described by Hadamard matrices (these turn out to be central in our proofs) we obtain a simple algebraic tractability criterion, which says that the tractable cases are those “representable” by a quadratic polynomial over the field.
登录
查看更多内容
影响因子：
3.9
作者：
M. Freedman;L. Lovász;A. Schrijver
通讯作者：
M. Freedman;L. Lovász;A. Schrijver
（几乎）随机均匀地选择 H 着色的复杂性
DOI：
--
发表时间：
2002
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
L. A. Goldberg;S. Kelk;M. Paterson
通讯作者：
M. Paterson
DOI：
--
发表时间：
2008
期刊：
European journal of combinatorics (Print)
影响因子：
--
作者：
L. Lovász;A. Schrijver
通讯作者：
A. Schrijver
DOI：
10.1145/1374376.1374488
发表时间：
2008
期刊：
Proceedings of the fortieth annual ACM symposium on Theory of computing
影响因子：
--
作者：
L. Barto;M. Kozik;T. Niven
通讯作者：
T. Niven
覆盖多项式的复杂度
DOI：
10.1007/978-3-540-73420-8_69
发表时间：
2007
期刊：
ArXiv
影响因子：
--
作者：
Markus Bläser;Holger Dell
通讯作者：
Holger Dell