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

Close Encounters with Boolean Functions of Three Different Kinds

Matthew Geoffrey Parker

Lecture notes in computer scienceAug 25, 20087 citations

A Dichotomy for Real Boolean Holant Problems

Shao, Shuai, Jin‐Yi Cai

We prove a complexity dichotomy for Holant problems on the boolean domain with arbitrary sets of real-valued constraint functions. These constraint functions need not be symmetric nor do we assume any auxiliary functions as in previous results. It is proved that for every set $\mathcal{F}$ of real-valued constraint functions, Holant $(\mathcal{F})$ is either P-time computable or #P-hard. The classification has an explicit criterion. This is the culmination of much research on this problem, and it uses previous results and techniques from many researchers. Some particularly intriguing concrete functions $f_6$ , $f_8$ and their associated families with extraordinary closure properties related to Bell states in quantum information theory play an important role in this proof.We prove a complexity dichotomy for Holant problems on the boolean domain with arbitrary sets of real-valued constraint functions. These constraint functions need not be symmetric nor do we assume any auxiliary functions as in previous results. It is proved that for every set $\mathcal{F}$ of real-valued constraint functions, Holant$(\mathcal{F})$ is either P-time computable or #P-hard. The classification has an explicit criterion. This is the culmination of much research on this problem, and it uses previous results and techniques from many researchers. Some particularly intriguing concrete functions $f_6$, $f_8$ and their associated families with extraordinary closure properties related to Bell states in quantum information theory play an important role in this proof.

arXiv:2005.07906May 16, 20201 citation

\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.

\mathcal{F}

of real-valued constraint functions, Holant

(\mathcal{F})

is either P-time computable or #P-hard. The classification has an explicit criterion. This is the culmination of much research on this problem, and it uses previous results and techniques from many researchers. Some particularly intriguing concrete functions

f_6

f_8

and their associated families with extraordinary closure properties related to Bell states in quantum information theory play an important role in this proof.