The complexity of counting homomorphisms seen from the other side
The complexity of counting homomorphisms seen from the other side
复制标题
从另一面看计算同态的复杂性
DOI：
10.1016/j.tcs.2004.08.008
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
P. Jonsson
中科院分区：
文献类型：
--
作者：
V. Dalmau;P. Jonsson
对于每一类关系结构C，设HOM（C,_）为判定结构a∈C是否与给定的任意结构b同态的问题。Grohe证明了在一定的复杂性理论假设下，当且仅当C中所有结构的核具有有界树宽时，HOM（C,_）在多项式时间内可解。我们证明了（在较弱的复杂性理论假设下）当且仅当C中的所有结构具有有界树宽度时，相应的计数问题# hm （C,_）在多项式时间内可解。这回答了高仪提出的一个悬而未决的问题。
For every class of relational structures C, let HOM(C,_) be the problem of deciding whether a structure A∈C has a homomorphism to a given arbitrary structure B. Grohe has proved that, under a certain complexity-theoretic assumption, HOM(C,_) is solvable in polynomial time if and only if the cores of all structures in C have bounded tree-width. We prove (under a weaker complexity-theoretic assumption) that the corresponding counting problem #HOM(C,_) is solvable in polynomial time if and only if all structures in C have bounded tree-width. This answers an open question posed by Grohe.