期刊
SIAM JOURNAL ON COMPUTING
卷 47, 期 3, 页码 798-828出版社
SIAM PUBLICATIONS
DOI: 10.1137/17M113304X
关键词
counting complexity; dichotomy; Holant; #CSP
资金
- National Natural Science Foundation of China [61170299, 61370053, 61572003]
Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Boolean Holant problems with nonnegative algebraic weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric and no auxiliary function is assumed to be available. Let F be a set of nonnegative functions defined on the Boolean domain. We show that the problem Holant(F) is computable in polynomial time if the function set F satisfies one of three conditions: (1) every function in F is a tensor product of functions of arity at most 2; (2) every function in F is affine; (3) F is holographically transformable to a product type by some real orthogonal matrix. Otherwise the problem is #P-hard.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据