THE COMPLEXITY OF BOOLEAN HOLANT PROBLEMS WITH NONNEGATIVE WEIGHTS

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.