Counting Homomorphisms and Partition Functions
Counting Homomorphisms and Partition Functions
复制标题
计算同态和配分函数
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
M. Thurley
中科院分区：
文献类型：
--
作者：
Martin Grohe;M. Thurley
关系结构之间的同态不仅是基本的数学对象，而且在应用计算环境中也是非常重要的。事实上，约束满足问题（CSP），在计算机科学的许多不同领域（如人工智能或数据库理论）中出现的一类广泛的算法问题，可以被视为要求两个关系结构之间的同态[FedVar98]。在逻辑环境中，同态可以被视为关系语言中的正本原公式的证明。正如我们将看到的，同态，或者更准确地说，两个结构之间的同态数，也与统计物理学的一个基本计算问题有关。
在本文中，我们关注的是计算从给定结构A到固定结构B的同态的复杂性。实际上，我们主要感兴趣的是将这个问题推广到加权同态（或配分函数）。我们几乎只关注图表。文章的第一部分是一个简短的调查什么是已知的问题。在第二部分中，我们给出了Bulatov和本文第一作者[BulGro05]的一个定理的证明，该定理对由具有非负元素的矩阵描述的划分函数的复杂性进行了分类。我们在这里给出的证明基本上与原来的证明相同，由于[Thu09]而有一些捷径，但它是用一种不同的、更图论的语言来表达的，这可能使它更容易被大多数读者所理解。
Homomorphisms between relational structures are not only fundamental mathematical objects, but are also of great importance in an applied computational context. Indeed, constraint satisfaction problems (CSPs), a wide class of algorithmic problems that occur in many different areas of computer science such as artificial intelligence or database theory, may be viewed as asking for homomorphisms between two relational structures [FedVar98]. In a logical setting, homomorphisms may be viewed as witnesses for positive primitive formulas in a relational language. As we shall see, homomorphisms, or more precisely the numbers of homomorphisms between two structures, are also related to a fundamental computational problem of statistical physics.
In this article, we are concerned with the complexity of counting homomorphisms from a given structure A to a fixed structure B. Actually, we are mainly interested in a generalization of this problem to weighted homomorphisms (or partition functions). We almost exclusively focus on graphs. The first part of the article is a short survey of what is known about the problem. In the second part, we give a proof of a theorem due to Bulatov and the first author of this paper [BulGro05], which classifies the complexity of partition functions described by matrices with non-negative entries. The proof we give here is essentially the same as the original one, with a few shortcuts due to [Thu09], but it is phrased in a different, more graph theoretical language that may make it more accessible to most readers.
登录
查看更多内容
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