The Complexity of Partition Functions on Hermitian Matrices
The Complexity of Partition Functions on Hermitian Matrices
复制标题
Hermitian 矩阵上配分函数的复杂性
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
M. Thurley
中科院分区：
文献类型：
--
作者：
M. Thurley
统计物理中某些“自旋玻璃”模型的配分函数与组合图不变量有很强的联系。也被称为同态函数，它们允许表示许多这样的不变量，例如，图的独立集合的数量或k流在任何地方都为零的数量。本文对复值配分函数的复杂性进行了研究，为配分函数复杂性研究的最新进展做出了贡献。这些函数通常由一个方阵a决定，Goldberg, Grohe， Jerrum和Thurley证明，对于每个实值对称矩阵，对应的配分函数要么是多项式时间可计算的，要么是#P-hard的。推广这一结果，给出了可由厄米矩阵定义的配分函数的复杂度的完整描述。这些也可以分为多项式时间可计算和#P-hard。虽然多项式时间可计算性的准则不能在一行中描述，但我们从与阿贝尔群相关的结构中给出了一个清晰的说明。
Partition functions of certain classes of "spin glass" models in statistical physics show strong connections to combinatorial graph invariants. Also known as homomorphism functions they allow for the representation of many such invariants, for example, the number of independent sets of a graph or the number nowhere zero k-flows. Contributing to recent developments on the complexity of partition functions we study the complexity of partition functions with complex values. These functions are usually determined by a square matrix A and it was shown by Goldberg, Grohe, Jerrum, and Thurley that for each real-valued symmetric matrix, the corresponding partition function is either polynomial time computable or #P-hard. Extending this result, we give a complete description of the complexity of partition functions definable by Hermitian matrices. These can also be classified into polynomial time computable and #P-hard ones. Although the criterion for polynomial time computability is not describable in a single line, we give a clear account of it in terms of structures associated with Abelian groups.
登录
查看更多内容
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
混合符号配分函数的复杂度二分法
影响因子：
1.6
作者：
Goldberg L
通讯作者：
Goldberg L
影响因子：
1
作者：
Dyer M
通讯作者：
Dyer M