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.

DOI: 10.48550/arxiv.2005.07906

Related papers

A Dichotomy for Real Boolean Holant Problems

Shuai Shao, 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. It is proved that for every set F of real-valued constraint functions, Holant(F) is either P-time computable or #P-hard. The classification has an explicit criterion. This is a culmination of much research on this problem, and it uses many previous results and techniques. Dealing with some concrete functions plays an important role in this proof. In particular, two functions, called f6 and f8, and their associated families exhibit intriguing and extraordinary closure properties related to Bell states in quantum information theory.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. It is proved that for every set F of real-valued constraint functions, Holant(F) is either P-time computable or #P-hard. The classification has an explicit criterion. This is a culmination of much research on this problem, and it uses many previous results and techniques. Dealing with some concrete functions plays an important role in this proof. In particular, two functions, called f6 and f8, and their associated families exhibit intriguing and extraordinary closure properties related to Bell states in quantum information theory.

Annual Symposium on Foundations of Computer ScienceNov 1, 202015 citations

A Complete Dichotomy for Complex-Valued Holant^c

Miriam Backens

Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holant^c denotes a subfamily of those problems, where any function set considered must contain the two unary functions pinning inputs to values 0 or 1. The complexity classification of Holant problems usually takes the form of dichotomy theorems, showing that for any set of functions in the family, the problem is either #P-hard or it can be solved in polynomial time. Previous such results include a dichotomy for real-valued Holant^c and one for Holant^c with complex symmetric functions. Here, we derive a dichotomy theorem for Holant^c with complex-valued, not necessarily symmetric functions. The tractable cases are the complex-valued generalisations of the tractable cases of the real-valued Holant^c dichotomy. The proof uses results from quantum information theory, particularly about entanglement.Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holant^c denotes a subfamily of those problems, where any function set considered must contain the two unary functions pinning inputs to values 0 or 1. The complexity classification of Holant problems usually takes the form of dichotomy theorems, showing that for any set of functions in the family, the problem is either #P-hard or it can be solved in polynomial time. Previous such results include a dichotomy for real-valued Holant^c and one for Holant^c with complex symmetric functions. Here, we derive a dichotomy theorem for Holant^c with complex-valued, not necessarily symmetric functions. The tractable cases are the complex-valued generalisations of the tractable cases of the real-valued Holant^c dichotomy. The proof uses results from quantum information theory, particularly about entanglement.

arXiv:1704.05798Leibniz international proceedings in informaticsApr 19, 20173 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

The Complexity of Holant Problems over Boolean Domain with Non-Negative 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 Holant problems over Boolean domain with non-negative weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric. Holant problems are indeed read-twice $\#$ CSPs. Intuitively, some $\#$ CSPs that are $\#$ P-hard become tractable when restricting to read-twice instances. To capture them, we introduce the Block-rank-one condition. It turns out that the condition leads to a clear separation. If a function set $\mathcal{F}$ satisfies the condition, then $\mathcal{F}$ is of affine type or product type. Otherwise (a) $\mathrm{Holant}(\mathcal{F})$ is $\#$ P-hard; or (b) every function in $\mathcal{F}$ is a tensor product of functions of arity at most 2; or (c) $\mathcal{F}$ is transformable to a product type by some real orthogonal matrix. Holographic transformations play an important role in both the hardness proof and the characterization of tractability.Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Holant problems over Boolean domain with non-negative weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric. Holant problems are indeed read-twice $\#$CSPs. Intuitively, some $\#$CSPs that are $\#$P-hard become tractable when restricting to read-twice instances. To capture them, we introduce the Block-rank-one condition. It turns out that the condition leads to a clear separation. If a function set $\mathcal{F}$ satisfies the condition, then $\mathcal{F}$ is of affine type or product type. Otherwise (a) $\mathrm{Holant}(\mathcal{F})$ is $\#$P-hard; or (b) every function in $\mathcal{F}$ is a tensor product of functions of arity at most 2; or (c) $\mathcal{F}$ is transformable to a product type by some real orthogonal matrix. Holographic transformations play an important role in both the hardness proof and the characterization of tractability.

arXiv:1611.00975Leibniz international proceedings in informaticsNov 3, 20167 citations

Dichotomy for Holant Problems of Boolean Domain

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

Holant problems are a general framework to study counting problems. Both counting Constraint Satisfaction Problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant ∗ (F), where F is a set of constraint functions on Boolean variables and output complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique and indeed the formulation of the theorem use holographic algorithms and reductions. By considering these counting problems over the complex domain, we discover surprising new tractable classes, which are associated with isotropic vectors, i.e., a (non-zero) vector whose inner product with itself is zero. 1Holant problems are a general framework to study counting problems. Both counting Constraint Satisfaction Problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant ∗ (F), where F is a set of constraint functions on Boolean variables and output complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique and indeed the formulation of the theorem use holographic algorithms and reductions. By considering these counting problems over the complex domain, we discover surprising new tractable classes, which are associated with isotropic vectors, i.e., a (non-zero) vector whose inner product with itself is zero. 1

Aug 14, 201034 citations

A complete dichotomy for complex-valued holantc

Miriam Backens

Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holantc denotes a subfamily of those problems, where any function set considered must contain the two unary functions pinning inputs to values 0 or 1. The complexity classification of Holant problems usually takes the form of dichotomy theorems, showing that for any set of functions in the family, the problem is either #P-hard or it can be solved in polynomial time. Previous such results include a dichotomy for real-valued Holantc and one for Holantc with complex symmetric functions, i.e. functions which only depend on the Hamming weight of the input. Here, we derive a dichotomy theorem for Holantc with complex-valued, not necessarily symmetric functions. The tractable cases are the complex-valued generalisations of the tractable cases of the real-valued Holantc dichotomy. The proof uses results from quantum information theory, particularly about entanglement. This full dichotomy for Holantc answers a question that has been open for almost a decade.Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holantc denotes a subfamily of those problems, where any function set considered must contain the two unary functions pinning inputs to values 0 or 1. The complexity classification of Holant problems usually takes the form of dichotomy theorems, showing that for any set of functions in the family, the problem is either #P-hard or it can be solved in polynomial time. Previous such results include a dichotomy for real-valued Holantc and one for Holantc with complex symmetric functions, i.e. functions which only depend on the Hamming weight of the input. Here, we derive a dichotomy theorem for Holantc with complex-valued, not necessarily symmetric functions. The tractable cases are the complex-valued generalisations of the tractable cases of the real-valued Holantc dichotomy. The proof uses results from quantum information theory, particularly about entanglement. This full dichotomy for Holantc answers a question that has been open for almost a decade.

Jul 13, 20189 citations

\mathcal{F}

of real-valued constraint functions, Holant

(\mathcal{F})

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.

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

\#

CSPs. Intuitively, some

\#

CSPs that are

\#

P-hard become tractable when restricting to read-twice instances. To capture them, we introduce the Block-rank-one condition. It turns out that the condition leads to a clear separation. If a function set

\mathcal{F}

satisfies the condition, then

\mathcal{F}

is of affine type or product type. Otherwise (a)

\mathrm{Holant}(\mathcal{F})

\#

P-hard; or (b) every function in

\mathcal{F}

is a tensor product of functions of arity at most 2; or (c)

\mathcal{F}

is transformable to a product type by some real orthogonal matrix. Holographic transformations play an important role in both the hardness proof and the characterization of tractability.