Journal
SIAM JOURNAL ON COMPUTING
Volume 47, Issue 3, Pages 798-828Publisher
SIAM PUBLICATIONS
DOI: 10.1137/17M113304X
Keywords
counting complexity; dichotomy; Holant; #CSP
Funding
- National Natural Science Foundation of China [61170299, 61370053, 61572003]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available