期刊
THEORETICAL COMPUTER SCIENCE
卷 982, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.tcs.2023.114256
关键词
Holant problems; Computational complexity; Dichotomy; SLOCC
This paper investigates the computational complexity classification of Holant problems on 3-regular graphs and provides corresponding conclusions.
Holant problem is a framework to study counting problems, which is expressive enough to contain Counting Graph Homomorphisms (#GH) and Counting Constraint Satisfaction Problems (#CSP) as special cases. In the present paper, we classify the computational complexity of Holant problems on 3-regular graphs, where the signature is complex valued and not necessarily symmetric. In details, we prove that Holant problem on 3-regular graphs is #P-hard except for the signature is not genuinely entangled, A-transformable, P-transformable or vanishing, in which cases the problem is tractable.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据