Holant is an essential framework in the field of counting complexity. For over fifteen years, researchers have been clarifying the complexity classification for complex-valued Holant on Boolean domain, a challenge that remains unresolved. In this article, we prove a complexity dichotomy for complex-valued Holant on Boolean domain when a non-trivial signature of odd arity exists. This dichotomy is based on the dichotomy for #EO, and consequently is an FP^NP vs. #P dichotomy as well, stating that each problem is either in FP^NP or #P-hard. Furthermore, we establish a generalized version of the decomposition lemma for complex-valued Holant on Boolean domain. It asserts that each signature can be derived from its tensor product with other signatures, or conversely, the problem itself is in FP^NP. We believe that this result is a powerful method for building reductions in complex-valued Holant, as it is also employed as a pivotal technique in the proof of the aforementioned dichotomy in this article.Holant is an essential framework in the field of counting complexity. For over fifteen years, researchers have been clarifying the complexity classification for complex-valued Holant on Boolean domain, a challenge that remains unresolved. In this article, we prove a complexity dichotomy for complex-valued Holant on Boolean domain when a non-trivial signature of odd arity exists. This dichotomy is based on the dichotomy for #EO, and consequently is an FP^NP vs. #P dichotomy as well, stating that each problem is either in FP^NP or #P-hard. Furthermore, we establish a generalized version of the decomposition lemma for complex-valued Holant on Boolean domain. It asserts that each signature can be derived from its tensor product with other signatures, or conversely, the problem itself is in FP^NP. We believe that this result is a powerful method for building reductions in complex-valued Holant, as it is also employed as a pivotal technique in the proof of the aforementioned dichotomy in this article.

arXiv:2502.05597Leibniz international proceedings in informaticsJan 1, 20250 citations

The Complexity of Boolean Holant Problems with Nonnegative Weights

Jiabao Lin, Hanpin Wang

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 $\mathcal{F}$ be a set of nonnegative functions defined on the Boolean domain. We show that the problem Holant $(\mathcal{F})$ is computable in polynomial time if the function set $\mathcal{F}$ satisfies one of three conditions: (1) every function in $\mathcal{F}$ is a tensor product of functions of arity at most 2; (2) every function in $\mathcal{F}$ is affine; (3) $\mathcal{F}$ is holographically transformable to a product type by some real orthogonal matrix. Otherwise the problem is #P-hard.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 $\mathcal{F}$ be a set of nonnegative functions defined on the Boolean domain. We show that the problem Holant$(\mathcal{F})$ is computable in polynomial time if the function set $\mathcal{F}$ satisfies one of three conditions: (1) every function in $\mathcal{F}$ is a tensor product of functions of arity at most 2; (2) every function in $\mathcal{F}$ is affine; (3) $\mathcal{F}$ is holographically transformable to a product type by some real orthogonal matrix. Otherwise the problem is #P-hard.

SIAM Journal on ComputingJan 1, 201825 citations

\mathcal{F}

be a set of nonnegative functions defined on the Boolean domain. We show that the problem Holant

(\mathcal{F})

is computable in polynomial time if the function set

\mathcal{F}

satisfies one of three conditions: (1) every function in

\mathcal{F}

is a tensor product of functions of arity at most 2; (2) every function in

\mathcal{F}

is affine; (3)

\mathcal{F}

is holographically transformable to a product type by some real orthogonal matrix. Otherwise the problem is #P-hard.