From an Odd Arity Signature to a Holant Dichotomy

Meng, Boning; Wang, Juqiu; Xia, Mingji; Zheng, Jiayi

doi:10.4230/LIPIcs.CCC.2025.23

From an Odd Arity Signature to a Holant Dichotomy

Boning Meng¹¹1The authors share first author status.

Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
University of Chinese Academy of Sciences, Beijing, China Juqiu Wang¹¹1The authors share first author status.

Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
University of Chinese Academy of Sciences, Beijing, China Mingji Xia¹¹1The authors share first author status.

Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
University of Chinese Academy of Sciences, Beijing, China Jiayi Zheng¹¹1The authors share first author status.

Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
University of Chinese Academy of Sciences, Beijing, China

Abstract

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 $\text{FP}^{\text{NP}}$ vs. #P dichotomy as well, stating that each problem is either in $\text{FP}^{\text{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 $\text{FP}^{\text{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.

Keywords and phrases:

Complexity dichotomy, Counting, Holant problem, #P

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Problems, reductions and completeness

Related Version:

Full Version: https://arxiv.org/abs/2502.05597 [25]

Funding:

All authors are supported by National Key R&D Program of China (2023YFA1009500) and NSFC 62272448.

DOI:

10.4230/LIPIcs.CCC.2025.23

Event:

40th Computational Complexity Conference (CCC 2025)

Editors:

Srikanth Srinivasan

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Counting complexity is an essential aspect of computational complexity. Basically, it focuses on computing the sum of the weights of the solutions. Holant is one of the most significant frameworks in the field of counting complexity, as it is capable of capturing a number of counting problems, such as counting perfect matchings in a graph or computing the partition function of the six-vertex model in statistical physics. There is a long history studying the complexity of Holant, and much progress has been made. On the other hand, however, the complete complexity classification of complex-valued Holant on Boolean domain remains unclear.

This article focuses on counting problems defined on Boolean domain and develops existing complexity dichotomies. It presents a full dichotomy for complex-valued Holant where there exists a non-trivial²²2By the term “non-trivial” we mean that the signature does not remain constant at 0. It can be easily verified that if a signature remains constant at 0, then removing such signature from the signature set would not change the complexity of the problem. signature of odd arity, which we denoted by complex $\textup{{Holant}}^{\text{odd}}$ for short. This dichotomy encompasses the previous results in [9, 3, 30], with the exception that it is an $\text{FP}^{\text{NP}}$ vs. #P dichotomy. Furthermore, this article also presents a decomposition lemma for complex-valued Holant based on the dichotomy in [24], which is the extension of a widely-used method originally developed in [22].

To begin with, Holant is a framework of counting problems parameterized by a signature set $\mathcal{F}$ , originally defined in [14]. Each signature of arity $r$ in $\mathcal{F}$ is a mapping from $\{0,1\}^{r}$ to $\mathbb{C}$ , representing a local constraint. Each input, or equivalently an instance of $\textup{{Holant}}(\mathcal{F})$ , is a grid $\Omega=(G,\pi)$ where $G$ is a graph³³3In this article, the term “graph” is understood to refer to a multi-graph. The presence of self-loops and parallel edges is invariably permitted. and $\pi$ assigns a signature to each vertex in $G$ . Each edge in $G$ is regarded as a variable subject to constraints imposed by incident vertices, and the output is the summation over the weights of all possible assignments of the variables, where the weight is the production of the output of each signature. See Definition 3 for a detailed definition.

Holant is considered as one of the most important frameworks in the field of counting complexity. On one hand, it is capable of expressing a considerable number of counting problems, such as counting matchings and counting perfect matchings in a graph (#Matching and #PM), counting weighted Eulerian orientations in a graph (#EO), counting constraint satisfaction problem (#CSP) and computing the partition function of the six-vertex and eight-vertex model. On the other hand, Holant was originally inspired by the discovery of the holographic algorithm [28, 29], which in turn was inspired by quantum computation and is closely related to the concept of Stochastic Local Operations and Classical Communication (SLOCC). Furthermore, several non-trivial connections between Holant and quantum computation have also been established [9, 2, 3, 18].

Consequently, Holant has attracted a number of researchers to classify the complexity of this framework. The ultimate goal in this study is to decide the complexity of $\textup{{Holant}}(\mathcal{F})$ for every complex-valued signature set $\mathcal{F}$ . It is believed that there exists a dichotomy for complex-valued Holant, which means that for arbitrary $\mathcal{F}$ , $\textup{{Holant}}(\mathcal{F})$ is either polynomial-time computable or #P-hard. Nevertheless, this hypothesis has been open for over 15 years, and currently the dichotomy result can only be stated for several types of signature sets. In the following, an overview of the research history is presented, along with a discussion of the current state of knowledge.

The research commences with symmetric signature sets, where the output of each signature only depends on the Hamming weight, or equivalently the number of 1’s, of the input. Consequently, a symmetric signature $f$ of arity $r$ can be expressed as $[f_{0},f_{1},\ldots,f_{r}]_{r}$ , where $f_{i}$ is the value of $f$ when the Hamming weight of the input is $i$ . Under this restriction, the Holant framework is denoted as sym-Holant. Besides, sometimes the dichotomy holds when some specific signatures are available. We use $\Delta_{0},\Delta_{1},\Delta_{+},\Delta_{-}$ to denote $[1,0],[0,1],[1,1],[1,-1]$ respectively. If all unary signatures are available, such problem is denoted as $\textup{{Holant}}^{*}$ ; if $\Delta_{0},\Delta_{1},\Delta_{+},\Delta_{-}$ are available, such problem is denoted as $\textup{{Holant}}^{+}$ ; if $\Delta_{0},\Delta_{1}$ are available, such problem is denoted as $\textup{{Holant}}^{c}$ . In particular, if a non-trivial signature of odd arity belongs to the signature set, we denote such problem as $\textup{{Holant}}^{\text{odd}}$ for convenience.

The previous results for symmetric cases are summarized in Table 2, and those for general cases are summarized in Table 2. By definition, the result of each individual cell encompasses both the results that are located in the same column above it and the results that are located in the same row to its left. Furthermore, several essential dichotomies for Holant not listed in the table are presented below without exhaustive explanation. These are dichotomies respectively for #CSP [16], six-vertex model [10], eight-vertex model [7], #EO [8, 23, 24] and a single ternary signature [30].

Table 1: Research history of Holant. The term ’/’ is same as that in Table 2.

	sym-Holant^∗	sym-Holant^c	sym-Holant
real-valued	/	[14]	[21]
complex-valued	[14]	[13]	[11]

Table 2: Research history of sym-Holant. The term ’/’ denotes that the corresponding dichotomy is directly encompassed by another dichotomy, thus obviating the necessity for separate research.

	Holant^∗	Holant⁺	Holant^c	$\textup{{Holant}}^{\text{odd}}$	Holant
nonnegative-valued	/	/	/	/	[22]
real-valued	/	/	[17]	[9]	[26]
complex-valued	[15]	[2]	[3]	Our result	Unknown

It is noticeable that except for the last column in Table 2, the majority of works concentrate on scenarios where specific signatures of odd arity are present. Furthermore, the number of such signatures decreases from left to right, being infinite, 4, 2, 1 (and 0 in the last column) respectively. This article proves a definitive conclusion to this series of works, the position of which is also presented in Table 2.

In order to reach this conclusion, it is necessary to extend the result of the decomposition lemma, originally developed in [22]. This lemma can derive a specific signature from its tensor product with other signatures, and has been employed in numerous recent works [8, 9, 26, 7, 24]. However, the general form of this lemma does not hold for all complex-valued signature sets.

On the other hand, a series of works has classified the complexity of counting weighted Eulerian orientations in a graph (#EO) [10, 8, 27, 23, 24]. An $\text{FP}^{\text{NP}}$ vs. #P dichotomy dichotomy is established in [24], which claims that a problem in #EO is either in $\text{FP}^{\text{NP}}$ or #P-hard. This motivates us to prove a generalized version of the decomposition lemma, stating that either the signature can be derived from the tensor product, or the complexity of the problem can be classified by the #EO dichotomy.

Consequently, there are two major results in this article, stated as follows. The detailed forms of them are Theorem 29 and Theorem 30, presented in Section 3. We use $\leq_{T}$ to denote polynomial-time Turing reduction and $\equiv_{T}$ to denote polynomial-time Turing equivalence. We use $\otimes$ to denote tensor product.

Theorem 1 (Decomposition lemma).

Let $\mathcal{F}$ be a set of signatures and $f$ , $g$ be two signatures. Then one of the following holds.

1.

$\textup{{Holant}}(\mathcal{F},f,g)\equiv_{T}\textup{{Holant}}(\mathcal{F},f% \otimes g)$ ;
2.

$\textup{{Holant}}(\mathcal{F},f\otimes g)$ is in $\text{FP}^{\text{NP}}$ .

Theorem 2 (Dichotomy for $\textup{{Holant}}^{\text{odd}}$ ).

Let $\mathcal{F}$ be a set of signatures that contains a non-trivial signature of odd arity. Then one of the following holds.

1.

$\textup{{Holant}}(\mathcal{F})$ is #P-hard;
2.

$\textup{{Holant}}(\mathcal{F})$ is in $\text{FP}^{\text{NP}}$ .

In some cases appearing in Theorem 1, $\textup{{Holant}}(\mathcal{F},f\otimes g)$ is #P-hard. In these cases, the reduction in the first statement trivially holds. We also remark that the definitions of complexity classes appearing in the two theorems can be found in [1]. In particular, the complexity class $\text{FP}^{\text{NP}}$ is introduced due to the dichotomy for #EO in [24], making Theorem 2 an $\text{FP}^{\text{NP}}$ vs. #P dichotomy. As analyzed in [24], such dichotomy can separate the computational complexity as well, unless the complexity class PH collapses at the second level. Furthermore, as shown in the proof strategy in Section 3, the proof of Theorem 2 is unfeasible in the absence of the dichotomy for #EO, hence the introduction of the complexity class $\text{FP}^{\text{NP}}$ is somehow inevitable. On the other hand, when the intermediate results are independent of the dichotomy for #EO, the $\text{FP}^{\text{NP}}$ term does not manifest. In other words, if a traditional FP vs. #P dichotomy is later proved for #EO, Theorem 2 will consequently become an FP vs. #P dichotomy as well.

Despite the $\text{FP}^{\text{NP}}$ part, this article makes a great progression towards the complexity classification of complex-valued Holant. With Theorem 2, it is now sufficient for future studies to focus on the case when all signatures in $\mathcal{F}$ are of even arity. With Theorem 1, we may further assume that these signatures are irreducible, and each realized signature does not contain a factor of odd arity. In addition, Theorem 2 also encompasses the preceding results in [9, 3, 30]. To the best of our knowledge, the dichotomy results in the field of complex-valued Holant that have not been yet encompassed are precisely those in [12, 26, 7, 24] and this article.

Figure 1: The reduction map for Holant with

\Delta_{0}

. We use

\textup{{K-Holant}}(\mathcal{F})

to denote

\textup{{Holant}}(\neq_{2}\mid\mathcal{F})

. We use the term “A

\to

B” to mean the corresponding reduction in our proof. It is noteworthy that a node may have multiple outgoing arcs, and in this case at least one of the reduction holds.

Figure 2: The reduction map for

\textup{{Holant}}^{\text{odd}}

. We use

\textup{{K-Holant}}(\mathcal{F})

to denote

\textup{{Holant}}(\neq_{2}\mid\mathcal{F})

. We use the term ’A

\to

B’ to mean the corresponding reduction in our proof. It is noteworthy that a node may have multiple outgoing arcs, and in this case at least one of the reduction holds.

The reductions in the proof of Theorem 2 are summarized as two maps, presented in Figure 1 and 2. Now we present the proof strategy for Theorem 2. Please refer to Section 2 for some specific definitions introduced in this strategy. The proof combines the techniques from the dichotomy for real-valued $\textup{{Holant}}^{\text{odd}}$ [9] and that for complex-valued $\textup{{Holant}}^{c}$ [3]. The structure of the proof is also a combination of those from the aforementioned references, and basically consists of four parts. In general, the structure can be stated as follows.

1.

Realize a non-trivial unary signature, and transform it into $\Delta_{0}$ through holographic transformation.
2.

Use $\Delta_{0}$ and self-loops to obtain an irreducible ternary signature $f$ .
3.

Realize a symmetric signature $h$ of GHZ type with $f$ .
4.

Transform $h$ into $[1,0,0,1]$ through holographic transformation, and reduce a certain #CSP to this problem.

Step 1 comes from [9], stated as Lemma 40. In Step 1, the proof uses self-loop to reduce the arity of the odd signature by 2 at a time, while keeping the obtained signature non-trivial. If this process fails, we deal with this case by [9, Theorem 5.3] with some slight modifications. Otherwise we may obtain a unary signature.

Step 2 also comes from [9]. In Step 2, we use $\Delta_{0}$ , self-loops and the technique of Unique Prime Factorization (UPF) to reduce the arity of an irreducible signature as in [9]. Again we can realize an irreducible ternary signature $f$ , or deal with other cases by the dichotomy in [3] or [17, Lemma 5.2] with some slight modifications on the origin proof. This part corresponds to the first part of Section 5.1.

Step 3 comes from [3]. We do not further reduce the arity of $f$ to 2 as this part of proof in [9] is quite dependent on the properties of real numbers. Rather, we use the knowledge from quantum entanglement theory to classify such $f$ into different types. We also use the methods developed in [3] to realize a symmetric signature $h$ of GHZ type for different types of signatures. This part corresponds to the last part of Section 5.1.

Step 4 involves the method in [13, Theorem 5], which is also employed in [3]. The only difference between this step and the corresponding proof in [3] is the inability to realize $\Delta_{1}$ . However, this does not introduce any challenges. This part corresponds to the middle part of Section 5.1.

On the other hand, we remark that nontrivial obstacles occur in Step 1, 2 and 3.

In Step 1, if the obtained signature is a multiple of $[1,\mathfrak{i}]$ or $[1,-\mathfrak{i}]$ , then the obtained unary signature may not be transformed into $\Delta_{0}$ . This special case does not appear in the setting of real-valued signatures, and consequently we need to analyze it separately. The analysis of this part includes a number of reductions, which induces a complicated reduction map, as presented in Figure 2. This obstacle is overcome in Section 5.2. We also remark that in these reductions, the dichotomies respectively for $\text{HW}^{\geq}$ , $\text{HW}^{\leq}$ and single-weighted signatures are employed, hence the complexity class $\text{FP}^{\text{NP}}$ is also introduced.

In Step 2, the UPF method employs the decomposition lemma from [22]. As the original lemma does not hold for all complex-valued signature sets, this motivated us to prove the generalized version of decomposition lemma, presented as Theorem 1.

In Step 3, due to the absence of $\Delta_{1}$ , we are not able to realize a symmetric $h$ of GHZ type for some $f$ of W type. Furthermore, for some specific $f$ , we may not even simulate $\Delta_{1}$ through polynomial interpolation. By carefully analyzing each possible case, we prove that for such $f$ , $\widehat{f}$ is restricted to be either $[-1,1,0,0]$ or $[0,0,1,-1]$ . For this specific case, we prove that the form of each other signature is also restricted to a specific form, otherwise again symmetric $h$ of GHZ type or $\Delta_{1}$ can be realized. This proof is challenging, as it involves detailed classification of signatures, a special holographic transformation to restrict the form of each signature, the UPF method for reducing the arity and a complicated analysis for the support of each signature. Finally, the only case left is when all signatures in $\mathcal{F}$ take this specific form, which induces the tractability. The proof of this part is also presented in Figure 1, and involves Lemma 51-56.

This article is organized as follows. In Section 2, we introduce preliminaries needed in this article. In Section 3, we present our main results in detail. In Section 4, we prove Theorem 1. In Section 5, we prove Theorem 2. In Section 6, we conclude our results.

2 Preliminaries

2.1 Definitions and notations

A Boolean domain refers to the set $\{0,1\}$ , or $\mathbb{F}_{2}$ for convenience to describe particular classes of tractable signatures. A complex-valued Boolean signature $f$ with $r$ variables is a mapping from $\{0,1\}^{r}$ to $\mathbb{C}$ . In particular, this article focuses on algebraic complex-valued Boolean signatures. Given a 01-string $\alpha$ with length $r$ , we use $f(\alpha)$ or $f_{\alpha}$ to denote the value of $f$ on the input $\alpha$ . The set of variables of $f$ is denoted by $\text{Var}(f)$ , and its size (or arity) is denoted by $\text{arity}(f)$ . The set of strings on which $f$ has non-zero values is the support of $f$ , denoted by $\text{supp}(f)$ .

Let $\alpha$ denote a binary string. For $s\in\{0,1\}$ , we use $\#_{s}(\alpha)$ to denote the number of occurrences of $s$ in $\alpha$ , and $\#_{1}(\alpha)$ is also known as the Hamming weight of $\alpha$ . The length of $\alpha$ is denoted by $\text{Len}(\alpha)$ , and $\alpha_{i}$ refers to its $i$ -th bit. We use $0_{k}$ and $1_{k}$ to denote the two strings of length $k$ that only contain 0 and 1 respectively. When the length $k$ is clear from the context, we use 0 and 1 to represent $0_{k}$ and $1_{k}$ .

The following notations from [23, 24] are employed in this article.

\text{HW}^{=}=\{\alpha\mid\#_{1}(\alpha)=\#_{0}(\alpha)\}\quad\text{and}\quad% \text{HW}^{\geq}=\{\alpha\mid\#_{1}(\alpha)\geq\#_{0}(\alpha)\}.

A signature $f$ is an $\text{HW}^{=}$ signature or equivalently an EO signature if $\text{supp}(f)\subseteq\text{HW}^{=}$ , and such signatures inherently have even arity. Analogously, $f$ is an $\text{HW}^{\geq}$ signature if $\text{supp}(f)\subseteq\text{HW}^{\geq}$ , and $\mathcal{F}$ is $\text{HW}^{\geq}$ if $\mathcal{F}$ only contains $\text{HW}^{\geq}$ signatures. Similar notations are also defined by replacing “ $\geq$ ” with “ $\leq$ ”, “ $<$ ”, or “ $>$ ”.

The bitwise addition (XOR) of two strings $\alpha$ and $\beta$ , denoted by $\alpha\oplus\beta$ , produces a string $\gamma$ where $\gamma_{i}=\alpha_{i}+\beta_{i}\pmod{2}$ for each $i$ . A set $A$ of strings is affine if $\alpha\oplus\beta\oplus\gamma\in A$ for arbitrary $\alpha,\beta,\gamma\in A$ . The affine span of a set $S$ is the minimal affine space containing $S$ . For a signature $f$ , $\text{Span}(f)$ denotes the affine span of its support.

A symmetric signature $f$ of arity $r$ is expressed as $[f_{0},f_{1},\ldots,f_{r}]_{r}$ , where $f_{i}$ is the value of $f$ on all inputs of Hamming weight $i$ and the subscript $r$ can be omitted without causing ambiguity. Commonly used examples include the unary signatures $\Delta_{0}=[1,0]$ and $\Delta_{1}=[0,1]$ , and the binary disequality signature $(\neq_{2})=[0,1,0]$ .

Let $\mathcal{EQ}$ denote the class of equality signatures, defined as $\mathcal{EQ}=\{=_{1},=_{2},\ldots,=_{r},\ldots\}$ , where $=_{r}$ is the signature $[1,0,\ldots,0,1]_{r}$ of arity $r$ . In other words, the output of $=_{r}$ is 1 if all bits of the input are identical (all 0’s or all 1’s), and is 0 otherwise.

The tensor product of signatures is denoted by $\otimes$ . We use $\langle\mathcal{F}\rangle$ to denote the closure of $\mathcal{F}$ under tensor products.

2.2 Frameworks of counting problems

In this subsection, we present pivotal frameworks of counting problems, including Holant and #CSP. We largely refer to [5, Section 1.2] and [8, Section 2.1].

Let $\mathcal{F}$ denote a fixed finite set of Boolean signatures. A signature grid over $\mathcal{F}$ , denoted as $\Omega(G,\pi)$ , consists of a graph $G=(V,E)$ and a mapping $\pi$ that assigns to each vertex $v\in V$ a signature $f_{v}\in\mathcal{F}$ , along with a fixed linear order of its incident edges. The arity of each signature $f_{v}$ matches the degree of $v$ , with each incident edge corresponding to a variable of $f_{v}$ . Throughout, we allow graphs to have parallel edges and self-loops. Given any 0-1 edge assignments $\sigma$ , the evaluation of the signature grid is given by the product $\prod_{v\in V}f_{v}(\sigma|_{E(v)})$ , where $\sigma|_{E(v)}$ represents the restriction of $\sigma$ to the edges incident to $v$ .

Definition 3 (Holant problems).

A Holant problem, $\textup{{Holant}}(\mathcal{F})$ , parameterized by a set $\mathcal{F}$ of complex-valued signatures, is defined as follows: Given an instance that is a signature grid $\Omega(G,\pi)$ over $\mathcal{F}$ , the output is the partition function of $\Omega$ ,

\textup{{Holant}}_{\Omega}=\sum_{\sigma:E\rightarrow\{0,1\}}\prod_{v\in V}f_{v% }(\sigma|_{E(v)}).

The bipartite Holant problem $\textup{{Holant}}(\mathcal{F}\mid\mathcal{G})$ is a specific case where $G$ is bipartite, say $G(U,V,E)$ , with vertices in $U$ assigned signatures from $\mathcal{F}$ and vertices in $V$ assigned signatures from $\mathcal{G}$ . We denote the left-hand side (or the right-hand side) in bipartite Holant briefly as LHS (or RHS).

For simplicity of presentation, we omit the curly braces when writing the set of one single signature. For example, we write $\textup{{Holant}}(\mathcal{F}\cup\{f\})$ as $\textup{{Holant}}(\mathcal{F},f)$ . In addition to bipartite Holant, there are several variants of Holant. We use $\textup{{Holant}}^{c}(\mathcal{F})$ to denote $\textup{{Holant}}(\mathcal{F},\Delta_{0},\Delta_{1})$ . We use $\textup{{K-Holant}}(\mathcal{F})$ to denote $\textup{{Holant}}(\neq_{2}\mid\mathcal{F})$ and $\textup{{K-Holant}}^{c}(\mathcal{F})$ to denote $\textup{{K-Holant}}(\mathcal{F},\Delta_{0},\Delta_{1})$ .

Another special variant of Holant is counting weighted Eulerian Orientations (#EO) [8]. However, we do not expand on the details here; readers are referred to [23, 24] for relevant works, as well as the full version of this paper [25].

The framework of #CSP is also closely related to Holant [14]. A variant of #CSP, denoted by $\textup{{\#CSP}}_{d}$ problems [21], also plays a role in our proof.

Definition 4 ( $\#\textup{{CSP}}$ ).

Let $\mathcal{F}$ be a fixed finite set of complex-valued signatures over the Boolean domain. An instance $I=(X,C)$ of $\#\textup{{CSP}}(\mathcal{F})$ consists of a finite variable set $X=\{x_{1},x_{2},\ldots,x_{n}\}$ and a clause set $C$ , where each clause $C_{i}\in C$ includes a signature $f_{i}=f\in\mathcal{F}$ (of arity $k$ ) and a selection of variables $(x_{i_{1}},x_{i_{2}},\ldots,x_{i_{k}})$ from $X$ , allowing repetition. The output of the instance is defined as:

\text{Z}(I)=\sum_{\begin{subarray}{c}x_{1},\ldots,x_{n}\in\{0,1\}\end{subarray% }}\prod_{(f,x_{i_{1}},\ldots,x_{i_{k}})\in C}f(x_{i_{1}},\ldots,x_{i_{k}}),

Definition 5.

Let $d\geq 1$ be an integer and let $\mathcal{F}$ be a set of complex-valued signatures. The problem $\textup{{\#CSP}}_{d}(\mathcal{F})$ is the restriction of $\textup{{\#CSP}}(\mathcal{F})$ to the instances where every variable occurs a multiple of $d$ times.

For an integer $d\geq 1$ , let $\mathcal{EQ}_{d}$ denote the class of equality signatures whose arities are divisible by $d$ , defined by $\mathcal{EQ}_{d}=\{=_{d},=_{2d},\ldots,=_{rd},\ldots\}$ . It is well-known that #CSP and $\textup{{\#CSP}}_{d}$ can be expressed within the Holant framework, as shown in the following lemmas. In this work, we apply polynomial-time Turing reductions (denoted by $\leq_{T}$ ) and equivalences (denoted by $\equiv_{T}$ ) to derive complexity classifications.

Lemma 6 ([5, Lemma 1.2]).

$\#\textup{{CSP}}(\mathcal{F})\equiv_{T}\textup{{Holant}}(\mathcal{EQ}\cup% \mathcal{F})$

Lemma 7.

For an integer $d\geq 1$ , $\textup{{\#CSP}}_{d}(\mathcal{F})\equiv_{T}\textup{{Holant}}(\mathcal{EQ}_{d}% \mid\mathcal{F}).$

2.3 Fundamental methods

In this subsection, we first introduce the theory of unique tensor decomposition for signatures. We then present three pivotal reduction techniques in the study of counting problems: gadget construction, polynomial interpolation, and holographic transformation.

2.3.1 Signature factorization

In the study of Holant problems, the algebraic structure of signatures plays a pivotal role. This section introduces the Unique Prime Factorization (UPF), which is a fundamental method of characterizing signatures.

A non-trivial signature $f$ is irreducible if it cannot be expressed as a tensor product $f=g\otimes h$ for non-constant signatures $g, h$ . Then we introduce the Unique Prime Factorization.

Lemma 8 ([8, Lemma 2.13]).

Every non-trivial signature $f$ has a prime factorization $f=g_{1}\otimes\cdots\otimes g_{k}$ , where each $g_{i}$ is irreducible, and the factorization is unique up to variable permutation and constant factors. That is to say, if $f=g_{1}\otimes\cdots\otimes g_{k}=h_{1}\otimes\cdots\otimes h_{\ell}$ , then $k=\ell$ , and there exists a permutation $\pi$ such that $g_{\pi(i)}=c_{i}h_{i}$ for each $1\leq i\leq k$ , where each $c_{i}$ is a constant.

2.3.2 Gadget construction and signature matrix

This subsection introduces two principal concepts in the study of counting problems: gadget construction and the signature matrix. Gadget construction is a critical reduction technique, and the signature matrix provides an algebraic representation bridging gadget construction with matrix multiplication. Please refer to [5] as well as the full version of this paper for details.

Let $\mathcal{F}$ denote a set of signatures. An $\mathcal{F}$ -gate is similar to a signature grid $\Omega(G,\pi)$ , while the edges of $G=(V,E,D)$ are partitioned into internal edges $E$ (edges that have two ends from $V$ ) and dangling edges $D$ (edges that are incident to a single vertex). Let $|E|=n$ and $|D|=m$ , with internal edges encoding variables $\{x_{1},\ldots,x_{n}\}$ and dangling edges corresponding to $\{y_{1},\ldots,y_{m}\}$ . The $\mathcal{F}$ -gate induces a signature $f:\{0,1\}^{m}\to\mathbb{C}$ defined by:

f(y_{1},\ldots,y_{m})=\sum_{\sigma:E\to\{0,1\}}\prod_{v\in V}f_{v}\left(\hat{% \sigma}|_{E(v)}\right),

where $\hat{\sigma}:E\cup D\to\{0,1\}$ extends $\sigma$ by incorporating the assignment $\mathbf{y}\in\{0,1\}^{m}$ to dangling edges, and $f_{v}$ denotes the signature assigned to vertex $v$ via $\pi$ . A signature $f$ is called realizable from $\mathcal{F}$ if it can be represented by an $\mathcal{F}$ -gate. If $E=\emptyset$ , the resulting signature is the tensor product $\bigotimes_{v\in V}f_{v}$ . We denote the set of all signatures realizable from $\mathcal{F}$ as $\textsf{S}(\mathcal{F})$ . For any signature set $\mathcal{F}$ and $f\in\textsf{S}(\mathcal{F})$ , it is shown in [5, Lemma 1.3] that $\textup{{Holant}}(\mathcal{F})\equiv_{T}\textup{{Holant}}(\mathcal{F},f)$ , which provides a powerful tool to build reductions.

Next we introduce the signature matrix, which is an algebraic representation of a given signature. This representation is conducive to computational convenience. For a signature $f:\{0,1\}^{r}\to\mathbb{C}$ with ordered variables $(x_{1},\ldots,x_{r})$ , its signature matrix with parameter $l$ is $M(f)\in\mathbb{C}^{2^{l}\times 2^{r-l}}$ . Its row indices correspond to the assignments to the first $l$ variables $(x_{1},...,x_{l})$ and its column indices correspond to the assignments to the remaining $r-l$ variables $(x_{l+1},...,x_{r})$ . The entry is the corresponding value of $f$ given the input that combines the row index and the column index. For even arity signatures, $l=r/2$ is commonly used. The matrix is denoted by $M_{x_{1}\cdots x_{l},x_{l+1}\cdots x_{r}}(f)$ or simply $M_{f}$ without causing ambiguity.

We address several operations in gadget construction. The first operation is adding a self-loop. Suppose $f$ is a signature and $\text{Var}(f)=\{x_{1},\ldots,x_{n}\}$ . Suppose $b$ is a binary signature with $M_{b}=\begin{pmatrix}b_{00}&b_{01}\\ b_{10}&b_{11}\end{pmatrix}$ . By adding a self-loop using a binary signature $b$ on $x_{1}$ and $x_{2}$ of $f$ we mean connecting $x_{1}$ to the first variable of $b$ and $x_{2}$ to the second variable of $b$ , obtaining a signature $f^{\prime}$ . Here we use x to denote $(x_{3},\ldots,x_{n})$ and we have: $f^{\prime}(\textbf{x})=b_{00}f(0,0,\textbf{x})+b_{01}f(0,1,\textbf{x})+b_{10}f% (1,0,\textbf{x})+b_{11}f(1,1,\textbf{x}).$ We use $\partial_{ij}f$ (or $\widehat{\partial_{ij}}\widehat{f}$ ) to denote the signature obtained by adding a self-loop using $=_{2}$ (or $\neq_{2}$ ) on $x_{i}$ and $x_{j}$ of $f$ (or $\widehat{f}$ ).

The second operation is pinning. Given $f$ as a signature, the pinning operation connects $\Delta_{0}$ or $\Delta_{1}$ to one of $f$ ’s variables. We use $f^{x_{1}=0}$ and $f^{x_{1}=1}$ to denote the resulting signature after connecting the first variable $x_{1}$ to $\Delta_{0}$ and $\Delta_{1}$ respectively.

Lemma 9 ([9, Lemma 3.9]).

Let $f$ be a signature of arity $n\geq 2$ . If for any index $i$ , by pinning the variable $x_{i}$ of $f$ to $0$ , we have $f^{x_{i}=0}\equiv 0$ , then $f_{\alpha}=0$ for any $\alpha$ satisfying $\#_{1}(\alpha)\neq n$ . Furthermore, if there is a pair of indices $\{j,k\}$ such that $\partial_{jk}f\equiv 0$ , then $f\equiv 0$ .

2.3.3 Holographic transformations and SLOCC

In the study of Holant problems, holographic transformations provide a powerful tool for complexity classification. This section formalizes key concepts and theorems, and presents their relation with quantum computation.

For any graph $G$ , a bipartite graph preserving the Holant value can be constructed via the 2-stretch operation: each edge $e$ is replaced by a path of length two, introducing a new vertex assigned $=_{2}$ . We present the equivalence that $\textup{{Holant}}(=_{2}\mid\mathcal{F})\equiv_{T}\textup{{Holant}}(\mathcal{F})$ , where $\mathcal{F}$ denotes a set of signatures.

Let $T\in\mathbf{GL}_{2}(\mathbb{C})$ be an invertible 2×2 matrix. For a signature $f$ of arity $n$ , represented as a column vector $f\in\mathbb{C}^{2^{n}}$ , the transformed signature is denoted by $Tf=T^{\otimes n}f$ . For a signature set $\mathcal{F}$ , we define $T\mathcal{F}=\{Tf\mid f\in\mathcal{F}\}$ . The transformation of contra-variant signatures (row vectors) is $fT^{-1}$ . When we write $T f$ or $T\mathcal{F}$ , $f$ and signatures in $\mathcal{F}$ are regarded as column vectors by default; similarly for $f T$ or $\mathcal{F}T$ as row vectors. We also use $T f$ to denote the matrix $M_{V,\text{Var}(f)-V}(Tf)$ , where $V$ is a subset of $\text{Var}(f)$ . Suppose $|V|=k$ , we have $M_{V,\text{Var}(f)-V}(Tf)=T^{\otimes k}M_{V,\text{Var}(f)-V}(f)\left(T^{% \mathrm{T}}\right)^{\otimes(n-k)}$ . Similarly, $M_{V,\text{Var}(f)-V}\left(fT^{-1}\right)=\left(T^{-\mathrm{T}}\right)^{% \otimes k}M_{V,\text{Var}(f)-V}(f)\left(T^{-1}\right)^{\otimes(n-k)}$ , where we briefly denote $(T^{-1})^{\mathrm{T}}$ as $T^{-\mathrm{T}}$ and $|V|=k$ .

Suppose $T\in\textbf{GL}_{2}(\mathbb{C})$ . A holographic transformation defined by $T$ applies $T$ to all signatures in the RHS and $T^{-1}$ to all signatures in the LHS. In other words, given a signature grid $\Omega=(H,\pi)$ of $\textup{{Holant}}(\mathcal{F}\mid\mathcal{G})$ , the transformed grid $\Omega^{\prime}=(H,\pi^{\prime})$ is an instance of $\textup{{Holant}}(\mathcal{F}T^{-1}\mid T\mathcal{G})$ .

Theorem 10 ([29]).

For any $T\in\mathbf{GL}_{2}(\mathbb{C})$ ,

\textup{{Holant}}(\mathcal{F}\mid\mathcal{G})\equiv_{T}\textup{{Holant}}(% \mathcal{F}T^{-1}\mid T\mathcal{G}).

Theorem 10 shows that holographic transformations preserve the complexity of bipartite Holant problems. We use $\mathscr{O}$ to denote all orthogonal matrices, that is $\mathscr{O}=\{O\in\textbf{GL}_{2}(\mathbb{C})\mid O^{\mathrm{T}}O=\begin{% pmatrix}1&0\\ 0&1\end{pmatrix}\}.$ Notably, any holographic transformation by $O\in\mathscr{O}$ keeps the binary Equality signature invariant: $(=_{2})O^{-1}=(=_{2})$ , hence $\textup{{Holant}}(=_{2}\mid\mathcal{F})\equiv_{T}\textup{{Holant}}(=_{2}\mid O% \mathcal{F})$ .

A pivotal holographic transformation employs $K^{-1}=\frac{1}{\sqrt{2}}\begin{bmatrix}1&-\mathfrak{i}\\ 1&\mathfrak{i}\end{bmatrix}$ , mapping $(=_{2})$ to the disequality signature $(=_{2})K=(\neq_{2})$ , yielding $\textup{{Holant}}(=_{2}\mid\mathcal{F})\equiv_{T}\textup{{Holant}}(\neq_{2}% \mid K^{-1}\mathcal{F})$ . We use $\widehat{f}$ and $\widehat{\mathcal{F}}$ to denote $K^{-1}f$ and $K^{-1}\mathcal{F}$ respectively, and $X=\begin{pmatrix}0&1\\ 1&0\end{pmatrix}$ to denote the signature matrix of $\neq_{2}$ . It can be verified that $K=\frac{1}{\sqrt{2}}\left(\begin{matrix}1&1\\ \mathfrak{i}&-\mathfrak{i}\end{matrix}\right)$ . Furthermore, with these notations, we have $\textup{{Holant}}(\mathcal{F})\equiv_{T}\textup{{K-Holant}}(\widehat{\mathcal{% F}})$ .

We are also interested in what kind of holographic transformations keeps $\neq_{2}$ invariant, and by direct computation we have the following lemma.

Lemma 11.

Let $\widehat{Q}=\begin{pmatrix}1/q&0\\ 0&q\end{pmatrix}$ or $\begin{pmatrix}0&1/q\\ q&0\end{pmatrix}$ , where $q\neq 0$ . Then $(\neq_{2})\widehat{Q}=(\neq_{2})$ and $\textup{{K-Holant}}(\mathcal{F})\equiv_{T}\textup{{K-Holant}}(\widehat{Q}^{-1}% \mathcal{F})$ . Furthermore, any matrix $A$ satisfying $(\neq_{2})A=(\neq_{2})$ is of the form $\begin{pmatrix}1/q&0\\ 0&q\end{pmatrix}$ or $\begin{pmatrix}0&1/q\\ q&0\end{pmatrix}$ , where $q\neq 0$ .

Sometimes, it is more convenient to study a Holant problem in the setting of K-Holant. As presented in Lemma 11, holographic transformations that keep $\neq_{2}$ invariant do not change the support of signatures on the RHS, except for a possible exchange of the symbol of $0$ and $1$ for all signatures. Consequently, many results are proved by analyzing the support in the setting of K-Holant. The following lemma is such an example, which is also useful in our proof.

Lemma 12 ([8]).

Let $\widehat{f}$ be a signature of arity $k\geq 3$ . If for any indices $1\leq i,j\leq k$ , by adding a self-loop on $x_{i}$ and $x_{j}$ of $\widehat{f}$ using $\neq_{2}$ , $\widehat{\partial_{ij}}\widehat{f}\equiv 0$ , then $\widehat{f}(\alpha)=0$ for arbitrary $\alpha$ with $0<\#_{1}(\alpha)<n$ .

A concept in the quantum computation theory called Stochastic Local Operations and Classical Communication (SLOCC) [4, 19] is a generalization of the holographic transformation, which allows distinct transformations on each qubits, or variables in the setting of Holant. For an $n$ -ary signature $f$ , SLOCC applies $M_{1}\otimes\cdots\otimes M_{n}$ with $M_{i}\in\mathbf{GL}_{2}(\mathbb{C})$ on $f$ . When $M_{i}=T$ for each $1\leq i\leq n$ , it is exactly the holographic transformation defined by $T$ . Backens [2] leveraged SLOCC to establish the dichotomy theorem for $\textup{{Holant}}^{+}$ and $\textup{{Holant}}^{c}$ , which implies relations between counting problems and the quantum computation theory.

Besides, a classification of ternary irreducible signatures under SLOCC is given in [19].

Lemma 13 ([19]).

Suppose $g$ is a ternary irreducible signature. Then one of the following holds.

1.

$g$ is of GHZ type. That is, $g=(M_{1}\otimes M_{2}\otimes M_{3})[1,0,0,1]$ ;
2.

$g$ is of W type. That is, $g=(M_{1}\otimes M_{2}\otimes M_{3})[0,1,0,0]$ ,

where $M_{1},M_{2},M_{3}\in\mathbf{GL}_{2}(\mathbb{C})$ .

2.3.4 Polynomial interpolation

Polynomial interpolation is a powerful tool to build reductions as well. Detailed information about it can be found in [5], and it is sufficient for us to use the following lemma in our proof, whose proof follows from polynomial interpolation.

Lemma 14.

In the setting of $\textup{{K-Holant}}(\widehat{\mathcal{F}})$ , if $(n+1)$ pairwise linearly independent unary signatures with $poly(n)$ -size can be realized in poly(n) time for any $n\in\mathbb{N}_{+}$ in the setting of K-Holant, then $\textup{{K-Holant}}(\widehat{\mathcal{F}},[1,-1])\leq_{T}\textup{{K-Holant}}(% \widehat{\mathcal{F}})$ .

2.4 Known dichotomies

In this section, we introduce important results of complexity classifications of counting problems.

2.4.1 #CSP and $\textup{{\#CSP}}_{d}$

Let $X=(x_{1},x_{2},\ldots,x_{d},1)^{\mathrm{T}}$ be a $(d+1)$ -dimensional column vector over $\mathbb{F}_{2}$ and $A$ be a matrix over $\mathbb{F}_{2}$ . The indicator function $\chi_{AX}$ takes value 1 when $AX=\mathbf{0}$ and 0 otherwise, which indicates an affine space.

Definition 15.

We denote by $\mathscr{A}$ the set of signatures which have the form $\lambda\cdot\chi_{AX}\cdot\mathfrak{i}^{L_{1}(X)+L_{2}(X)+\cdots+L_{n}(X)}$ , where $\mathfrak{i}$ is the imaginary unit, $\lambda\in\mathbb{C}$ , $n\in\mathbb{Z}_{+}$ . Each $L_{j}$ is a 0-1 indicator function of the form $\langle\alpha_{j},X\rangle$ , where $\alpha_{j}$ is a $(d+1)$ -dimensional vector over $\mathbb{F}_{2}$ , and the dot product $\langle\cdot,\cdot\rangle$ is computed over $\mathbb{F}_{2}$ .

Definition 16.

We denote by $\mathscr{P}$ the set of all signatures which can be expressed as a product of unary signatures, binary equality signatures ( $=_{2}$ ) and binary disequality signatures ( $\neq_{2}$ ) on not necessarily disjoint subsets of variables.

The following property will be used in our proof, which can be verified from Definition 15 and 16 directly.

Lemma 17.

Suppose $f, g$ are binary signatures and $M_{f}=M_{g}^{-1}$ . Then $f\in\mathscr{A}$ (or $\mathscr{P}$ ) if and only if $g\in\mathscr{A}$ (or $\mathscr{P}$ respectively).

Now we can state the vital theorem that classifies complex-valued Boolean #CSP problems as follows:

Theorem 18 ([16, Theorem 3.1]).

Suppose $\mathcal{F}$ is a finite set of signatures mapping Boolean inputs to complex numbers. If $\mathcal{F}\subseteq\mathscr{A}$ or $\mathcal{F}\subseteq\mathscr{P}$ , then $\#\textup{{CSP}}(\mathcal{F})$ is computable in polynomial time. Otherwise, $\#\textup{{CSP}}(\mathcal{F})$ is #P-hard.

Next we introduce the complexity classification of $\textup{{\#CSP}}_{d}(\mathcal{F})$ . In this article, we focus on the case that $d=2$ and a special case that $\neq_{2}\in\mathcal{F}$ . Let $\rho_{d}=\text{e}^{\frac{i\pi}{2d}}$ be a $4d$ -th primitive root of unity, $T_{d}=\begin{pmatrix}1&0\\ 0&\rho_{d}\end{pmatrix},$ and $\mathscr{A}_{d}^{r}=\{T_{d}^{r}f\mid f\in\mathscr{A}\}$ , where $r\in[d]$ . A signature $f:\{0,1\}^{n}\rightarrow\mathbb{C}$ is called local affine if it satisfies $(\bigotimes_{j=1}^{n}T_{2}^{\alpha_{j}})f\in\mathscr{A}$ for any $\alpha\in\text{supp}(f)$ . The set of all local affine signatures is denoted by $\mathscr{L}$ . The dichotomies are stated as follows.

Theorem 19 ([17]).

Suppose $\mathcal{F}$ is a finite set of signatures. If $\mathcal{F}\subseteq\mathscr{A},\mathscr{P},\mathscr{A}_{2}^{1}$ or $\mathscr{L}$ , then $\textup{{\#CSP}}_{2}(\mathcal{F})$ is polynomial-time computable, otherwise it is #P-hard.

Theorem 20 ([9, Theorem 5.3]).

Let $\mathcal{F}$ be a set of complex-valued signatures. If $\mathcal{F}\subseteq\mathscr{P}$ or $\mathcal{F}\subseteq\mathscr{A}_{d}^{r}$ for some $r\in[d]$ , then $\textup{{\#CSP}}_{d}(\neq_{2},\mathcal{F})$ is tractable; otherwise, $\textup{{\#CSP}}_{d}(\neq_{2},\mathcal{F})$ is #P-hard.

2.4.2 $\textup{{Holant}}^{c}$

Several important notations and definitions are introduced.

Definition 21.

We use following notations.

$\blacksquare$

$\mathcal{T}$ is the set of all unary and binary signatures.
$\blacksquare$

$\mathcal{E}:=\{f\mid\exists\alpha\in\{0,1\}^{arity(f)}\text{ such that }f(x)=0% \text{ if }x\notin\{\alpha,\overline{\alpha}\}\}$ .
$\blacksquare$

$\mathcal{M}:=\{f\mid f(x)=0\text{ if }\#_{1}(x)>1\}$ is the set of weighted matching signatures.
$\blacksquare$

$\mathcal{B}:=\{M\mid M^{\mathrm{T}}\{=_{2},\Delta_{0},\Delta_{1}\}\subseteq% \mathscr{A}\}$ .

Definition 22.

We say a signature set $\mathcal{F}$ is $\mathscr{C}$ -transformable if there exists a $M\in\textbf{GL}_{2}(\mathbb{C})$ such that $=_{2}M\in\mathscr{C}$ and $M^{-1}\mathcal{F}\subseteq\mathscr{C}$ .

Theorem 23 ([3, Theorem 59]).

Let $\mathcal{F}$ be finite. Then $\textup{{Holant}}^{c}(\mathcal{F})$ is #P-hard unless:

1.

$\mathcal{F}\subseteq\left\langle\mathcal{T}\right\rangle$ ;
2.

$\mathcal{F}\cup\{\Delta_{0},\Delta_{1}\}$ is $\mathscr{P}$ -transformable. Equivalently, there exists $O\in\mathscr{O}$ such that $\mathcal{F}\subseteq\left\langle O\mathcal{E}\right\rangle$ , or $\mathcal{F}\subseteq\left\langle K\mathcal{E}\right\rangle=\left\langle KX% \mathcal{E}\right\rangle$ ;
3.

$\mathcal{F}\subseteq\left\langle K\mathcal{M}\right\rangle$ or $\mathcal{F}\subseteq\left\langle KX\mathcal{M}\right\rangle$ ;
4.

$\mathcal{F}\cup\{\Delta_{0},\Delta_{1}\}$ is $\mathscr{A}$ -transformable. Equivalently, there exists $B\in\mathcal{B}$ such that $\mathcal{F}\subseteq B\mathscr{A}$ ;
5.

$\mathcal{F}\subseteq\mathscr{L}$ .

In all of the exceptional cases, $\textup{{Holant}}^{c}(\mathcal{F})$ is polynomial-time computable.

We remark that, if $\mathcal{F}\subseteq\langle\mathcal{T}\rangle$ , then $\textup{{Holant}}(\mathcal{F})$ is polynomial-time computable directly by sequential matrix multiplication.

2.4.3 K-Holant

Let $f$ be an EO signature of arity $2d$ with $\text{Var}(f)=\{x_{1},x_{2},\ldots,x_{2d}\}$ . For an arbitrary perfect pairing $P$ of $\text{Var}(f)$ , say $P=\{\{x_{i_{1}},x_{i_{2}}\},\{x_{i_{3}},x_{i_{4}}\},\ldots,\{x_{i_{2d-1}},x_{i% _{2d}}\}\}$ , we define $\textup{{EO}}^{P}$ as the subset of $\{0,1\}^{2d}$ satisfying that $\textup{{EO}}^{P}=\{\alpha\in\{0,1\}^{2d}\mid\alpha_{i_{1}}\neq\alpha_{i_{2}},% \ldots,\alpha_{i_{2d-1}}\neq\alpha_{i_{2d}}\}.$

Definition 24.

Suppose $f$ is an arity $2d$ EO signature and $S\subseteq\text{HW}^{=}$ . $f|_{S}$ is the restriction of $f$ to $S$ , which means when $\alpha\in S$ , $f|_{S}(\alpha)=f(\alpha)$ , otherwise $f|_{S}(\alpha)=0$ .

If for any perfect pairing $P$ of Var $(f)$ , $f|_{\textup{{EO}}^{P}}\in\mathscr{A}$ , then we say that $f$ is $\textup{{EO}}^{\mathscr{A}}$ .

Similarly, if for any perfect matching $P$ of Var $(f)$ , $f|_{\textup{{EO}}^{P}}\in\mathscr{P}$ , then $f$ is $\textup{{EO}}^{\mathscr{P}}$ .

Definition 25.

Let $f$ be an EO signature. If for arbitrary $\alpha,\beta,\gamma\in\text{supp}(f)$ and $\delta=\alpha\oplus\beta\oplus\gamma$ , either $\delta\in\text{HW}^{>}$ (or $\delta\in\text{HW}^{<}$ respectively) or $\delta\in\text{supp}(f)$ holds, then $f$ is a $\forall 3\hskip 1.99997pt\mathbin{\leavevmode\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Meng% .latexml-figure0.pdf}}}}$ signature (or a $\forall 3\hskip 1.99997pt\mathbin{\leavevmode\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Meng% .latexml-figure1.pdf}}}}$ signature respectively).

Theorem 26 ([23, 24]).

Let $\mathcal{F}$ be a set of EO signatures. $\mathcal{F}$ is called #EO-quasi-tractable when the following conditions hold:

$\blacksquare$

All signatures in $\mathcal{F}$ are $\forall 3\hskip 1.99997pt\mathbin{\leavevmode\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Meng% .latexml-figure2.pdf}}}}$ signatures, or all signatures in $\mathcal{F}$ are $\forall 3\hskip 1.99997pt\mathbin{\leavevmode\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\hbox{{\leavevmode\includegraphics{}{}{dagpub-tikzpictures/p023-Meng% .latexml-figure3.pdf}}}}$ signatures;
$\blacksquare$

$\mathcal{F}\subseteq\textup{{EO}}^{\mathscr{A}}$ , or $\mathcal{F}\subseteq\textup{{EO}}^{\mathscr{P}}$ .

$\textup{{K-Holant}}(\mathcal{F})$ is #P-hard, unless $\mathcal{F}$ is #EO-quasi-tractable, in which cases it is in $\text{FP}^{\text{NP}}$ .

For a signature $f$ , we use $f|_{\textup{{EO}}}$ to denote the signature which satisfies that $f|_{\textup{{EO}}}(\alpha)=f(\alpha)$ if $\alpha\in\text{HW}^{=}$ , and $f|_{\textup{{EO}}}(\alpha)=0$ otherwise. This notation is consistent with Definition 24 by regarding the symbol EO as $\text{HW}^{=}$ . We use $\mathcal{F}|_{\textup{{EO}}}$ to denote the set $\{f|_{\textup{{EO}}}\mid f\in\mathcal{F}\}$ . A direct corollary of Theorem 26 is the dichotomy for K-Holant problems defined by $\text{HW}^{\geq}$ (or $\text{HW}^{\leq}$ ) signatures.

Corollary 27 ([24]).

Suppose $\mathcal{F}$ is a set of $\text{HW}^{\geq}$ (or $\text{HW}^{\leq}$ respectively) signatures. Then $\textup{{K-Holant}}(\mathcal{F})$ is #P-hard, unless $\mathcal{F}|_{\textup{{EO}}}$ is #EO-quasi-tractable, in which cases it is in $\text{FP}^{\text{NP}}$ .

At last we introduce the dichotomy for K-Holant problems defined by single-weighted signatures. Suppose $f$ is a signature of arity $k$ . If $f$ takes the value $0$ on all input strings whose Hamming weight is not equal to $d$ , where $d$ is an integer satisfying $0\leq d\leq k$ , then we say $f$ is a single-weighted signature.

For each single-weighted signature $f\in\mathcal{F}$ of arity $k$ which can only take non-zero values at Hamming weight $d,0\leq d\leq k$ , let

f_{\to\textup{{EO}}}=\begin{cases}f\otimes\Delta_{0}^{2d-k}&2d\geq k;\\ f\otimes\Delta_{1}^{k-2d},&2d<k.\end{cases}

Let $\mathcal{F}_{\to\textup{{EO}}}=\{f_{\to\textup{{EO}}}|f\in\mathcal{F}\}$ . Then we can state the dichotomy for K-Holant problems defined by single-weighted signatures.

Theorem 28 ([24]).

Suppose $\mathcal{F}$ is a set of single-weighted signatures. Then $\textup{{K-Holant}}(\mathcal{F})$ is #P-hard, unless one of the following holds, in which cases it is in $\text{FP}^{\text{NP}}$ .

1.

All signatures in $\mathcal{F}$ are $\text{HW}^{\geq}$ (or $\text{HW}^{\leq}$ respectively) signatures, and $\mathcal{F}|_{\textup{{EO}}}$ is #EO-quasi-tractable;
2.

There exist a non- $\text{HW}^{\geq}$ signature and a non- $\text{HW}^{\leq}$ signature belonging to $\mathcal{F}$ , and $\mathcal{F}_{\to\textup{{EO}}}$ is #EO-quasi-tractable.

3 Main results

In this section, we present our main results in detail. The first result is the generalized decomposition lemma, which can be applied within the complex-valued Holant framework and provides a powerful tool to make complexity classifications. We give the proof of the following theorem in Section 4.

Theorem 29 (Decomposition lemma).

Let $\mathcal{F}$ be a set of signatures and $f$ , $g$ be two signatures. Then

\textup{{Holant}}(\mathcal{F},f,g)\equiv_{T}\textup{{Holant}}(\mathcal{F},f% \otimes g)

holds unless $\widehat{\mathcal{F}}^{\prime}$ only contains $\text{HW}^{\geq}$ signatures (or $\text{HW}^{\leq}$ signatures respectively), where $\widehat{\mathcal{F}}^{\prime}$ denotes $\widehat{\mathcal{F}}\cup\{\widehat{f}\otimes\widehat{g}\}$ . In the latter situation, if $\widehat{\mathcal{F}}^{\prime}|_{\textup{{EO}}}$ is #EO-quasi-tractable, then $\textup{{Holant}}(\mathcal{F},f\otimes g)$ is in $\text{FP}^{\text{NP}}$ . Otherwise it is #P-hard.

The second result is the dichotomy for complex-valued $\textup{{Holant}}^{\text{odd}}$ . The proof of it is in Section 5.3.

Theorem 30 (Dichotomy for $\textup{{Holant}}^{\text{odd}}$ ).

Let $\mathcal{F}$ be a set of signatures that contains a non-trivial signature of odd arity, then $\textup{{Holant}}(\mathcal{F})$ is #P-hard unless:

1.

$\widehat{\mathcal{F}}$ only contains $\text{HW}^{\geq}$ signatures (or $\text{HW}^{\leq}$ signatures respectively), and $\widehat{\mathcal{F}}|_{\textup{{EO}}}$ is #EO-quasi-tractable;
2.

All signatures in $\widehat{\mathcal{F}}$ are single-weighted, there exist a non- $\text{HW}^{\geq}$ signature and a non- $\text{HW}^{\leq}$ signature belonging to $\widehat{\mathcal{F}}$ , and $\widehat{\mathcal{F}}_{\to\textup{{EO}}}$ is #EO-quasi-tractable;
3.

$\mathcal{F}\subseteq\langle\mathcal{T}\rangle$ ;
4.

$\mathcal{F}\subseteq\langle K\mathcal{M}\rangle$ or $\mathcal{F}\subseteq\langle KX\mathcal{M}\rangle$ ;
5.

$\mathcal{F}$ is $\mathscr{A}$ -transformable;
6.

$\mathcal{F}$ is $\mathscr{P}$ -transformable;
7.

$\mathcal{F}$ is $\mathscr{L}$ -transformable;

In case 1, 2, $\textup{{Holant}}(\mathcal{F})$ is in $\text{FP}^{\text{NP}}$ ; in case 3–7, $\textup{{Holant}}(\mathcal{F})$ is polynomial time computable. We denote Case 1–7 as condition ( $\mathcal{PC}$ ).

$\blacktriangleright$ Remark 31.

In case 1, 2 of condition ( $\mathcal{PC}$ ), there are parts of situations where the problem is actually polynomial time computable. One typical example is vanishing signatures. Suppose $\mathcal{F}$ is a set of signatures. It is called vanishing if the partition functions of all instances of $\textup{{Holant}}(\mathcal{F})$ are 0. By Lemma 39, if $\widehat{\mathcal{F}}$ is $\text{HW}^{<}$ or $\text{HW}^{>}$ , or equivalently $\mathcal{F}$ is vanishing, then $\textup{{Holant}}(\mathcal{F})$ is polynomial-time computable. We do not address these classes in this article, and the detailed information can be found in [23, 24].

The proof of Theorem 30 consists of two parts. Firstly, we prove a dichotomy for complex-valued Holant when $\Delta_{0}$ is available, stated as Lemma 32 in the following. In particular, we remark that it is a traditional FP vs. #P dichotomy. The reduction map of it is presented as Figure 1. Then we prove the dichotomy for complex-valued $\textup{{Holant}}^{\text{odd}}$ based on this dichotomy, whose reduction map is presented as Figure 2.

Lemma 32.

Let $\mathcal{F}$ be a set of signatures, then $\textup{{Holant}}(\mathcal{F},\Delta_{0})$ is #P-hard unless:

1.

$\mathcal{F}\subseteq\langle\mathcal{T}\rangle$ ;
2.

$\mathcal{F}\subseteq\langle K\mathcal{M}\rangle$ or $\mathcal{F}\subseteq\langle KX\mathcal{M}\rangle$ ;
3.

$\mathcal{F}\cup\{\Delta_{0}\}$ is $\mathscr{A}$ -transformable;
4.

$\mathcal{F}$ is $\mathscr{P}$ -transformable;
5.

$\mathcal{F}\cup\{\Delta_{0}\}$ is $\mathscr{L}$ -transformable;

in which cases, $\textup{{Holant}}(\mathcal{F},\Delta_{0})$ is polynomial-time computable.

4 Decomposition lemma

In this chapter, we present the generalized decomposition lemma, which demonstrates that, under certain conditions, $\textup{{Holant}}(f,g,\mathcal{F})\equiv_{T}\textup{{Holant}}(f\otimes g,% \mathcal{F})$ , otherwise the computational complexity of $\textup{{Holant}}(f\otimes g,\mathcal{F})$ is known. The proof of this result relies on some preliminary lemmas, which are presented in the following.

Lemma 33 ([22, Lemma 3.1]).

For any signature set $\mathcal{F}$ and signature $f$ ,

\textup{{Holant}}(\mathcal{F},f)\leq_{T}\textup{{Holant}}(\mathcal{F},f^{% \otimes d})

for all $d\geq 1$ .

Lemma 34 ([22, Lemma 3.2]).

Let $\mathcal{F}$ be a set of signatures, and $f$ , $g$ be two signatures. Suppose that there exists an instance $\Omega$ of $\textup{{Holant}}(\mathcal{F},f,g)$ such that $\textup{{Holant}}_{\Omega}\neq 0$ , and the number of occurrences of $g$ in $\Omega$ is greater than that of $f$ . Then

\textup{{Holant}}(\mathcal{F},f,f\otimes g)\leq_{T}\textup{{Holant}}(\mathcal{% F},f\otimes g).

Lemma 35 ([22, Corollary 3.3]).

Let $\mathcal{F}$ be a set of signatures, and $f$ , $g$ be two signatures. If $g$ is not vanishing, then

\textup{{Holant}}(\mathcal{F},f,f\otimes g)\leq_{T}\textup{{Holant}}(\mathcal{% F},f\otimes g).

$\blacktriangleright$ Remark 36.

As mentioned in [8], the unique prime factorization of a signature $f$ naturally divides $\text{Var}(f)$ into several sets, each corresponding to a prime factor of $f$ . It can be easily verified that the partition of $\text{Var}(f)$ remains unchanged under holographic transformation (even SLOCC). Therefore, we can apply the three lemmas above in the setting of K-Holant.

Lemma 37.

Suppose $f$ is a signature and $\alpha\in\text{supp}(f)$ . Suppose $\#_{0}(\alpha)-\#_{1}(\alpha)=k>0$ (or $\#_{1}(\alpha)-\#_{0}(\alpha)=k>0$ ), then a signature $g$ of arity $k$ can be obtained by adding self-loops using $\neq_{2}$ on $f$ such that $g(\textbf{0})\neq 0$ (or $g(\textbf{1})\neq 0$ respectively).

Corollary 38.

Suppose $f$ is an $\text{HW}^{>}$ (or $\text{HW}^{<}$ ) signature, by adding self-loop by $\neq_{2}$ we can always obtain $\lambda\Delta_{1}^{\otimes r}$ (or $\lambda\Delta_{0}^{\otimes r}$ ), where $r>0$ is an integer.

Symmetric vanishing signatures have been characterized in [12]. The following lemma characterizes vanishing signatures not necessarily to be symmetric.

Lemma 39.

Suppose $f$ is a signature and $\widehat{f}=K^{-1}f$ . Then the following two statements are equivalent:

1.

$f$ is vanishing;
2.

$\widehat{f}$ is a $\text{HW}^{>}$ or $\text{HW}^{<}$ signature.

5 Dichotomy for $\textup{{Holant}}^{\text{odd}}$

In this chapter, we prove the dichotomy for complex-valued $\textup{{Holant}}^{\text{odd}}$ . We emphasize that in the proofs of this chapter, we often normalize signatures by default for convenience, since this operation does not affect the computational complexity. For example, we write $\lambda\Delta_{0},\lambda\neq 0$ as $\Delta_{0}$ by default. By Theorem 29, we can always assume the signatures in $\mathcal{F}$ are irreducible in this section. We commence with the following lemmas, which separate $\textup{{Holant}}^{\text{odd}}$ into several cases.

Lemma 40.

Suppose $f\in\mathcal{F}$ is a non-trivial signature of odd arity. Then one of the following statements holds:

1.

There exists some matrix $Q\in\mathbb{C}^{2\times 2}$ such that $\textup{{Holant}}(Q\mathcal{F},\Delta_{0})\leq_{T}\textup{{Holant}}(\mathcal{F})$ ;
2.

$\textup{{K-Holant}}(\widehat{\mathcal{F}},\Delta_{0})\leq_{T}\textup{{Holant}}% (\mathcal{F})$ ;
3.

$\textup{{K-Holant}}(\widehat{\mathcal{F}},\Delta_{1})\leq_{T}\textup{{Holant}}% (\mathcal{F})$ ;
4.

$\textup{{K-Holant}}(\widehat{\mathcal{F}},[a,0,\dots,0,b]_{2k+1})\leq_{T}% \textup{{Holant}}(\mathcal{F})$ for some $k\in\mathbb{N}_{+}$ , where $ab\neq 0$ .

In the following, we classify the complexity of each case in Lemma 40 respectively. In Section 5.1, we deal with Case 1 and prove Lemma 32. In Section 5.2, we deal with other cases. In Section 5.3 we present the proof of Theorem 30.

5.1 A dichotomy for Holant problems when $\Delta_{0}$ is available

In this section, we prove Lemma 32. The reductions appearing in this section are summarized as a map in Figure 1.

If $\mathcal{F}\subseteq\mathcal{T}$ , $\textup{{Holant}}(\mathcal{F},\Delta_{0})$ is polynomial-time computable. As a result, we may assume there exists an irreducible signature $f\in\mathcal{F}$ with $\text{arity}(f)\geq 3$ . By replacing the original decomposition lemma by our generalized version Theorem 29, the following result, which previously only holds for real-valued Holant [9, Lemma 1.8], can be extended to complex-valued Holant.

Lemma 41.

Suppose $f\in\mathcal{F}$ is irreducible with $\text{arity}(f)\geq 3$ . Then one of the following holds.

1.

There is a ternary irreducible $g\in\textsf{S}(f,\Delta_{0})$ ;
2.

There is a quaternary $g\in\textsf{S}(f,\Delta_{0})$ satisfying $M_{g}=\begin{pmatrix}a&0&0&b\\ 0&0&0&0\\ 0&0&0&0\\ c&0&0&d\\ \end{pmatrix},ad-bc\neq 0$ ;
3.

$\Delta_{1}\in\textsf{S}(f,\Delta_{0})$ .

The complexity of the third situation can be classified by Theorem 23. The following lemmas can be used to deal with the second situation. Combining them with Theorem 19, the complexity classification of the second situation is done.

Lemma 42 ([6, Part of Lemma 2.40]).

Suppose $f\in\textsf{S}(\mathcal{F})$ satisfying $M_{f}=\begin{pmatrix}a&0&0&b\\ 0&0&0&0\\ 0&0&0&0\\ c&0&0&d\\ \end{pmatrix},$ $ad-bc\neq 0$ . Then $\textup{{Holant}}(\mathcal{F},=_{4})\equiv_{T}\textup{{Holant}}(\mathcal{F})$ .

Lemma 43 ([17, Lemma 5.2]).

Suppose $(=_{4})\in\mathcal{F}$ . Then $\textup{{Holant}}(\mathcal{F})\equiv_{T}\textup{{\#CSP}}_{2}(\mathcal{F})$ .

We now focus on the first situation. First, we show that the complexity can be classified if there exists a symmetric signature of GHZ type. A symmetric signature of GHZ type is denoted as the generic case in [13]. We present the following lemmas from [13]. It is noteworthy that the concept of $\omega$ -normalized signature is important in the following known lemmas, but its explicit definition does not need to be understood in our proof.

Lemma 44 ([13]).

Suppose $g$ is a symmetric signature of GHZ type, then there exists $M\in\mathbf{GL}_{2}(\mathbb{C})$ such that $g=M[1,0,0,1]$ .

Lemma 45 ([13]).

Suppose $[y_{0},y_{1},y_{2}]$ is $\omega$ -normalized and nondegenerate, and one of the following holds:

1.

$y_{0}\neq 0$ or $y_{2}\neq 0$ ;
2.

$y_{0}=y_{2}=0$ , and there exists a unary $\omega$ -normalized signature $[a,b]\in\mathcal{G}_{1}$ satisfying $ab\neq 0$ .

Then,

\textup{{Holant}}(\mathcal{G}_{1},[y_{0},y_{1},y_{2}]\mid\mathcal{G}_{2},=_{3}% )\equiv_{T}\textup{{\#CSP}}(\mathcal{G}_{1},\mathcal{G}_{2},[y_{0},y_{1},y_{2}])

Let $\Omega_{3}=\{\omega\mid\omega^{3}=1\}$ . To apply Lemma 45, the following facts would be useful.

Lemma 46 ([13]).

$[0,1,0]$ is $\omega$ -normalized.

For any symmetric binary signature $f$ , there exists $M_{\omega}=\begin{pmatrix}1&0\\ 0&\omega\end{pmatrix},\omega\in\Omega_{3}$ such that $fM_{\omega}$ is $\omega$ -normalized.

For any unary signature $f=[a,b],ab\neq 0$ , there exists $M_{\omega}=\begin{pmatrix}1&0\\ 0&\omega\end{pmatrix},\omega\in\Omega_{3}$ such that $fM_{\omega}$ is $\omega$ -normalized.

Now we are ready to prove the following lemma.

Lemma 47.

Suppose $g$ is a symmetric signature of GHZ type, then there exists an invertible matrix $N$ such that

\textup{{Holant}}(\mathcal{F},g,\Delta_{0})\equiv_{T}\textup{{\#CSP}}(=_{2}N,% \Delta_{0}N,N^{-1}\mathcal{F},N^{-1}\Delta_{0})

Noticing that by Lemma 47, once a symmetric ternary signature of GHZ type is realized, we can apply the complexity classification from the #CSP dichotomy. Backens also presents methods for symmetrization [2, 3]. Using those methods, we can realize a symmetric signature of GHZ type in most situations.

Lemma 48 ([2]).

Suppose $f$ is of GHZ type. Then there exists an irreducible symmetric signature $h\in\textsf{S}(\{f\})$ .

Lemma 49 ([2]).

Suppose $f$ is of W type and $f\notin\langle K\mathcal{M}\rangle\cup\langle KX\mathcal{M}\rangle$ . Then there exists a symmetric signature $h\in\textsf{S}(\{f\})$ of GHZ type.

Lemma 50 ([2]).

Suppose there is an irreducible ternary signature $f\in K\mathcal{M}$ and a binary signature $g\notin\langle K\mathcal{M}\rangle$ . Then there exists a symmetric signature $h\in\textsf{S}(\{f,g\})$ of GHZ type. The same statement also holds after replacing $K\mathcal{M}$ with $KX\mathcal{M}$ .

In the following analysis, we assume there is an irreducible ternary signature $f\in K\mathcal{M}\cap\mathcal{F}$ , and the analysis when $f\in KX\mathcal{M}$ is similar. Furthermore, we consider this case in the setting of K-Holant. We remark that $K^{-1}\Delta_{0}=[1,1]$ .

We begin with the analysis of $\widehat{f}$ .

Lemma 51.

Suppose $\widehat{g}\in\widehat{\mathcal{F}}$ satisfies $M_{\widehat{g}}=\begin{pmatrix}a&b\\ c&0\end{pmatrix},abc\neq 0$ . Then,

\textup{{K-Holant}}(\widehat{\mathcal{F}},[1,1])\equiv_{T}\textup{{Holant}}^{c% }(\mathcal{F})

Lemma 52.

Suppose $\widehat{f}\in\mathcal{M}\cap\widehat{\mathcal{F}}$ is an irreducible ternary function and not a multiple of $[-1,1,0,0]$ . Then,

\textup{{K-Holant}}(\widehat{\mathcal{F}},[1,1])\equiv_{T}\textup{{Holant}}^{c% }(\mathcal{F})

By Lemma 52 and Theorem 23, the only unsolved case is when $\widehat{f}=[-1,1,0,0]$ . Consequently we can assume $[-1,1,0,0]\in\widehat{\mathcal{F}}$ . In this case, firstly we consider the form of unary and binary signatures in $\widehat{\mathcal{F}}$ .

Lemma 53.

Suppose $[-1,1,0,0],\widehat{g}\in\widehat{\mathcal{F}}$ , where $\widehat{g}=[a,1],a\neq 1$ . Then

\textup{{K-Holant}}(\widehat{\mathcal{F}},[1,1])\equiv_{T}\textup{{Holant}}^{c% }(\mathcal{F})

Lemma 54.

Suppose $[-1,1,0,0],\widehat{g}\in\widehat{\mathcal{F}}$ , where $\widehat{g}$ is an irreducible binary signature and not a multiple of $[0,1,0]$ . Then one of the following holds:

1.

There exists an invertible matrix $N$ such that

$\textup{{Holant}}(\mathcal{F},\Delta_{0})\equiv_{T}\textup{{\#CSP}}(=_{2}N,% \Delta_{0}N,N^{-1}\mathcal{F},N^{-1}\Delta_{0})$ .
2.

$\textup{{K-Holant}}(\widehat{\mathcal{F}},[1,1])\equiv_{T}\textup{{Holant}}^{c% }(\mathcal{F})$ .

This result can also be extended to irreducible ternary signatures.

Lemma 55.

Suppose $[-1,1,0,0],\widehat{g}\in\widehat{\mathcal{F}}$ , where $\widehat{g}$ is an irreducible ternary signature and not a multiple of $[-1,1,0,0]$ . Then one of the following holds:

1.

There exists an invertible matrix $N$ such that

$\textup{{Holant}}(\mathcal{F},\Delta_{0})\equiv_{T}\textup{{\#CSP}}(=_{2}N,% \Delta_{0}N,N^{-1}\mathcal{F},N^{-1}\Delta_{0}).$
2.

$\textup{{K-Holant}}(\widehat{\mathcal{F}},[1,1])\equiv_{T}\textup{{Holant}}^{c% }(\mathcal{F})$ .

By Lemma 53, 54 and 55, the only case left is that all irreducible unary, binary and ternary signatures in $\widehat{\mathcal{F}}$ belong to $\{\Delta_{0},[1,1],[0,1,0],[-1,1,0,0]\}$ . The following lemma analyzes this last case.

Lemma 56.

Suppose $[-1,1,0,0]\in\widehat{\mathcal{F}}$ and $\mathcal{R}=\{\Delta_{0}\}\cup\{[-k,1,0,\ldots,0]_{k+2}\mid k\geq-1\}$ . Then one of the following statements holds:

1.

$\widehat{\mathcal{F}}\subseteq\langle\mathcal{R}\rangle$ .
2.

An irreducible signature $\widehat{h}\notin\mathcal{R}$ with arity less than 4 can be realized in the setting of $\textup{{K-Holant}}(\widehat{\mathcal{F}},[1,1])$ .

It is noteworthy that when $\widehat{\mathcal{F}}\subseteq\langle\mathcal{R}\rangle\subseteq\langle% \mathcal{M}\rangle$ , $\textup{{K-Holant}}(\widehat{\mathcal{F}})$ is polynomial time computable. When the second statement holds, by Lemma 53, 54 and 55, the complexity classification of $\textup{{Holant}}(\mathcal{F})$ is done.

5.2 Other cases

In this section, we classify the complexity of Case 2-4 in Lemma 40. The reductions in this section are summarized as a map, presented as Figure 2. We commence with the following lemmas employed in Case 4.

Lemma 57 ([9, Lemma 5.2]).

For any $k\geq 3$ , $\textup{{\#CSP}}_{k}(\neq_{2},F)\leq_{T}\textup{{K-Holant}}(=_{k},F)$ .

Lemma 58.

For arbitrary integer $k\geq 3$ and $ab\neq 0$ , there exists $\widehat{Q}\in\mathbb{C}^{2\times 2}$ such that $\textup{{\#CSP}}_{k}(\neq_{2},\widehat{Q}\widehat{\mathcal{F}})\leq_{T}\textup% {{K-Holant}}(\widehat{\mathcal{F}},[a,0,\dots,0,b]_{k})$ .

Lemma 59.

If $\textup{{\#CSP}}_{k}(\neq_{2},\widehat{Q}\widehat{\mathcal{F}})$ is tractable, then $\textup{{K-Holant}}(\widehat{\mathcal{F}},[a,0,\dots,0,b]_{k})$ is also tractable.

Lemma 59 can be proved by directly checking the tractable cases of $\textup{{\#CSP}}_{k}$ problems and holographic transformation. Combining Lemma 58 and 59 we have $\textup{{\#CSP}}_{k}(\neq_{2},\widehat{Q}\widehat{\mathcal{F}})\equiv_{T}% \textup{{K-Holant}}(\widehat{\mathcal{F}},[a,0,\dots,0,b]_{k})$ , which completes the complexity classification in Case 4.

For Case 2 and 3 in Lemma 40, we have the following lemma.

Lemma 60.

Let $c\in\{0,1\}$ . Then one of the following statements holds:

1.

All signatures in $\widehat{\mathcal{F}}\cup\{\Delta_{c}\}$ are $\text{HW}^{\geq}$ (or $\text{HW}^{\leq}$ respectively);
2.

$\textup{{Holant}}(Q\mathcal{F},\Delta_{0},[1,(-1)^{c}\mathfrak{i}])\equiv_{T}% \textup{{K-Holant}}(\widehat{\mathcal{F}},\Delta_{c})$ for some $Q\in\mathscr{O}$ ;
3.

$\textup{{K-Holant}}^{c}(\widehat{\mathcal{F}})\equiv_{T}\textup{{K-Holant}}(% \widehat{\mathcal{F}},\Delta_{c})$ .

The complexity of the first and second situation in Lemma 60 is already classified in Theorem 27 and Lemma 32. We now focus on the situation that the third statement holds.

Lemma 61.

Suppose $\widehat{f}$ is of arity $k\geq 3$ , $\alpha,\beta\in\text{supp}(\widehat{f})$ and one of $\alpha,\beta$ is not in $\{0_{k},1_{k}\}$ . Then there exists a signature $\widehat{f^{\prime}}$ satisfying the following conditions.

$\blacksquare$

$\textup{{K-Holant}}^{c}(\widehat{f},\widehat{f^{\prime}})\equiv_{T}\textup{{K-% Holant}}^{c}(\widehat{f})$ and arity $(\widehat{f^{\prime}})<k$ .
$\blacksquare$

$\alpha^{\prime},\beta^{\prime}\in\text{supp}(\widehat{f^{\prime}})$ and $\#_{1}(\alpha^{\prime})-\#_{1}(\beta^{\prime})=\#_{1}(\alpha)-\#_{1}(\beta)$ .

Lemma 62.

One of the following statements holds for $\textup{{K-Holant}}^{c}(\widehat{\mathcal{F}})$ .

1.

All signatures in $\widehat{\mathcal{F}}$ are single-weighted.
2.

There exists a $\widehat{Q}=\begin{pmatrix}1/r&0\\ 0&r\end{pmatrix}$ such that $\textup{{K-Holant}}^{c}(\widehat{Q}\widehat{\mathcal{F}},[1,0,\dots,0,1]_{k})% \equiv_{T}\textup{{K-Holant}}^{c}(\widehat{\mathcal{F}}).$

In the first statement of Lemma 62, the complexity of $\textup{{K-Holant}}^{c}(\widehat{\mathcal{F}})$ is already classified by Theorem 28. In the second statement of Lemma 62, when $k\geq 3$ , the complexity is already classified by Lemma 58 and 59. When $k=1$ , the complexity is already classified by Lemma 32. By the following lemma and Theorem 23 we complete the complexity classification when $k=2$ .

Lemma 63.

$\textup{{Holant}}^{c}(\widehat{\mathcal{F}},\neq_{2})\equiv_{T}\textup{{K-% Holant}}^{c}(\widehat{\mathcal{F}},=_{2})$ .

5.3 Proof of the main theorem

In preparation for the proof of Theorem 30, we introduce an important lemma.

Lemma 64.

Let $\mathcal{F}$ be a set of complex-valued signatures that satisfies condition ( $\mathcal{PC}$ ). Then for any $O\in\mathscr{O}$ , $O\mathcal{F}$ satisfies condition ( $\mathcal{PC}$ ).

We remark that by Lemma 64 and reduction to absurdity, for any $O\in\mathscr{O}$ , if $\mathcal{F}$ does not satisfy condition ( $\mathcal{PC}$ ), then $O\mathcal{F}$ also does not satisfy condition ( $\mathcal{PC}$ ). A direct corollary is presented in the following.

Corollary 65.

Let $\mathcal{F}$ be a set of complex-valued signatures and $\mathcal{F}$ does not satisfy condition ( $\mathcal{PC}$ ). Then for any $O\in\mathscr{O}$ , $\textup{{\#CSP}}(O\mathcal{F})$ , $\textup{{\#CSP}}_{2}(O\mathcal{F})$ , $\textup{{Holant}}^{c}(O\mathcal{F})$ , $\textup{{K-Holant}}(K^{-1}O\mathcal{F})$ are #P-hard.

6 Conclusion

In this article, we prove a generalized decomposition lemma for complex-valued Holant. Based on this lemma, we further prove a dichotomy for Holant when a non-trivial signature of odd arity exists ( $\textup{{Holant}}^{\text{odd}}$ ).

We emphasize that this dichotomy for $\textup{{Holant}}^{\text{odd}}$ is still an $\text{FP}^{\text{NP}}$ vs. #P dichotomy due to the dichotomy for #EO in [24]. As stated in [24], a specific problem defines the NP oracle and leads to the study of Boolean constraint satisfaction problems [20]. It is our hope that a complete complexity classification of this kind of problems can be established in the future.

Furthermore, it is worthwhile to pursuit the dichotomy for complex-valued Holant. By Theorem 29 and 30, the only remaining case is when all signatures in $\mathcal{F}$ are of even arity and irreducible. Nevertheless, the analysis of this case may present significant challenges, as was evidenced in the proof of its sub-cases [26, 7].

References

[1] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
[2] Miriam Backens. A new Holant dichotomy inspired by quantum computation. arXiv preprint arXiv:1702.00767, 2017. arXiv:1702.00767.
[3] Miriam Backens. A full dichotomy for Holant^c, inspired by quantum computation. SIAM Journal on Computing, 50(6):1739–1799, 2021.
[4] Charles H Bennett, Sandu Popescu, Daniel Rohrlich, John A Smolin, and Ashish V Thapliyal. Exact and asymptotic measures of multipartite pure-state entanglement. Physical Review A, 63(1):012307, 2000.
[5] Jin-Yi Cai and Xi Chen. Complexity dichotomies for counting problems: Volume 1, Boolean domain. Cambridge University Press, 2017.
[6] Jin-Yi Cai and Zhiguo Fu. Holographic algorithm with matchgates is universal for planar #CSP over Boolean domain. SIAM Journal on Computing, 51(2):STOC17–50, 2019.
[7] Jin-Yi Cai and Zhiguo Fu. Complexity classification of the eight-vertex model. Information and Computation, 293:105064, 2023. doi:10.1016/j.ic.2023.105064.
[8] Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. Beyond #CSP: A dichotomy for counting weighted Eulerian orientations with ARS. Information and Computation, 275:104589, 2020. doi:10.1016/j.ic.2020.104589.
[9] Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. From Holant to quantum entanglement and back. arXiv preprint, 2020. arXiv:2004.05706.
[10] Jin-Yi Cai, Zhiguo Fu, and Mingji Xia. Complexity classification of the six-vertex model. Information and Computation, 259:130–141, 2018. doi:10.1016/j.ic.2018.01.003.
[11] Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 635–644. Association for Computing Machinery, 2013. doi:10.1145/2488608.2488687.
[12] Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 635–644, 2013.
[13] Jin-Yi Cai, Sangxia Huang, and Pinyan Lu. From Holant to #CSP and back: Dichotomy for Holant^c problems. Algorithmica, 64:511–533, 2012. doi:10.1007/s00453-012-9626-6.
[14] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Holant problems and counting CSP. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, pages 715–724. Association for Computing Machinery, 2009. doi:10.1145/1536414.1536511.
[15] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for Holant* problems of Boolean domain. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1714–1728. SIAM, 2011. doi:10.1137/1.9781611973082.132.
[16] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted Boolean #CSP. Journal of Computer and System Sciences, 80(1):217–236, 2014. doi:10.1016/j.jcss.2013.07.003.
[17] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for real $\text{Holant}^{c}$ problems. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1802–1821. SIAM, 2018. doi:10.1137/1.9781611975031.118.
[18] Jin-Yi Cai and Ben Young. Planar #CSP equality corresponds to quantum isomorphism–a Holant viewpoint. ACM Transactions on Computation Theory, 16(3):1–41, 2024. doi:10.1145/3689486.
[19] Wolfgang Dür, Guifre Vidal, and J Ignacio Cirac. Three qubits can be entangled in two inequivalent ways. Physical Review A, 62(6):062314, 2000.
[20] Tomás Feder and Daniel Ford. Classification of bipartite boolean constraint satisfaction through delta-matroid intersection. SIAM Journal on Discrete Mathematics, 20(2):372–394, 2006. doi:10.1137/S0895480104445009.
[21] Sangxia Huang and Pinyan Lu. A dichotomy for real weighted Holant problems. computational complexity, 25:255–304, 2016. doi:10.1007/s00037-015-0118-3.
[22] Jiabao Lin and Hanpin Wang. The complexity of Boolean Holant problems with nonnegative weights. SIAM Journal on Computing, 47(3):798–828, 2018. doi:10.1137/17M113304X.
[23] Boning Meng, Juqiu Wang, and Mingji Xia. P-time algorithms for typical #EO problems. arXiv preprint, 2024. doi:10.48550/arXiv.2410.11557.
[24] Boning Meng, Juqiu Wang, and Mingji Xia. The $\text{FP}^{\text{NP}}$ versus #P dichotomy for #EO, 2025. doi:10.48550/arXiv.2502.02012.
[25] Boning Meng, Juqiu Wang, Mingji Xia, and Jiayi Zheng. From an odd arity signature to a Holant dichotomy, 2025. doi:10.48550/arXiv.2502.05597.
[26] Shuai Shao and Jin-Yi Cai. A dichotomy for real Boolean Holant problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1091–1102. IEEE, 2020. doi:10.1109/FOCS46700.2020.00105.
[27] Shuai Shao and Zhuxiao Tang. Eulerian orientations and Hadamard codes: A novel connection via counting. arXiv preprint, 2024. doi:10.48550/arXiv.2411.02612.
[28] Leslie G. Valiant. Accidental algorthims. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’06, pages 509–517. IEEE Computer Society, 2006. doi:10.1109/FOCS.2006.7.
[29] Leslie G Valiant. Holographic algorithms. SIAM Journal on Computing, 37(5):1565–1594, 2008. doi:10.1137/070682575.
[30] Peng Yang, Yuan Huang, and Zhiguo Fu. The computational complexity of Holant problems on 3-regular graphs. Theoretical Computer Science, 982:114256, 2024. doi:10.1016/j.tcs.2023.114256.

[bib.bib1] [1] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.

[bib.bib2] [2] Miriam Backens. A new Holant dichotomy inspired by quantum computation. arXiv preprint arXiv:1702.00767, 2017. arXiv:1702.00767.

[bib.bib3] [3] Miriam Backens. A full dichotomy for Holant^c, inspired by quantum computation. SIAM Journal on Computing, 50(6):1739–1799, 2021.

[bib.bib4] [4] Charles H Bennett, Sandu Popescu, Daniel Rohrlich, John A Smolin, and Ashish V Thapliyal. Exact and asymptotic measures of multipartite pure-state entanglement. Physical Review A, 63(1):012307, 2000.

[bib.bib5] [5] Jin-Yi Cai and Xi Chen. Complexity dichotomies for counting problems: Volume 1, Boolean domain. Cambridge University Press, 2017.

[bib.bib6] [6] Jin-Yi Cai and Zhiguo Fu. Holographic algorithm with matchgates is universal for planar #CSP over Boolean domain. SIAM Journal on Computing, 51(2):STOC17–50, 2019.

[bib.bib7] [7] Jin-Yi Cai and Zhiguo Fu. Complexity classification of the eight-vertex model. Information and Computation, 293:105064, 2023. doi:10.1016/j.ic.2023.105064.

[bib.bib8] [8] Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. Beyond #CSP: A dichotomy for counting weighted Eulerian orientations with ARS. Information and Computation, 275:104589, 2020. doi:10.1016/j.ic.2020.104589.

[bib.bib9] [9] Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. From Holant to quantum entanglement and back. arXiv preprint, 2020. arXiv:2004.05706.

[bib.bib10] [10] Jin-Yi Cai, Zhiguo Fu, and Mingji Xia. Complexity classification of the six-vertex model. Information and Computation, 259:130–141, 2018. doi:10.1016/j.ic.2018.01.003.

[bib.bib11] [11] Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 635–644. Association for Computing Machinery, 2013. doi:10.1145/2488608.2488687.

[bib.bib12] [12] Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 635–644, 2013.

[bib.bib13] [13] Jin-Yi Cai, Sangxia Huang, and Pinyan Lu. From Holant to #CSP and back: Dichotomy for Holant^c problems. Algorithmica, 64:511–533, 2012. doi:10.1007/s00453-012-9626-6.

[bib.bib14] [14] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Holant problems and counting CSP. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, pages 715–724. Association for Computing Machinery, 2009. doi:10.1145/1536414.1536511.

[bib.bib15] [15] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for Holant* problems of Boolean domain. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1714–1728. SIAM, 2011. doi:10.1137/1.9781611973082.132.

[bib.bib16] [16] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted Boolean #CSP. Journal of Computer and System Sciences, 80(1):217–236, 2014. doi:10.1016/j.jcss.2013.07.003.

[bib.bib17] [17] Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Dichotomy for real $\text{Holant}^{c}$ problems. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1802–1821. SIAM, 2018. doi:10.1137/1.9781611975031.118.

[bib.bib18] [18] Jin-Yi Cai and Ben Young. Planar #CSP equality corresponds to quantum isomorphism–a Holant viewpoint. ACM Transactions on Computation Theory, 16(3):1–41, 2024. doi:10.1145/3689486.

[bib.bib19] [19] Wolfgang Dür, Guifre Vidal, and J Ignacio Cirac. Three qubits can be entangled in two inequivalent ways. Physical Review A, 62(6):062314, 2000.

[bib.bib20] [20] Tomás Feder and Daniel Ford. Classification of bipartite boolean constraint satisfaction through delta-matroid intersection. SIAM Journal on Discrete Mathematics, 20(2):372–394, 2006. doi:10.1137/S0895480104445009.

[bib.bib21] [21] Sangxia Huang and Pinyan Lu. A dichotomy for real weighted Holant problems. computational complexity, 25:255–304, 2016. doi:10.1007/s00037-015-0118-3.

[bib.bib22] [22] Jiabao Lin and Hanpin Wang. The complexity of Boolean Holant problems with nonnegative weights. SIAM Journal on Computing, 47(3):798–828, 2018. doi:10.1137/17M113304X.

[bib.bib23] [23] Boning Meng, Juqiu Wang, and Mingji Xia. P-time algorithms for typical #EO problems. arXiv preprint, 2024. doi:10.48550/arXiv.2410.11557.

[bib.bib24] [24] Boning Meng, Juqiu Wang, and Mingji Xia. The $\text{FP}^{\text{NP}}$ versus #P dichotomy for #EO, 2025. doi:10.48550/arXiv.2502.02012.

[bib.bib25] [25] Boning Meng, Juqiu Wang, Mingji Xia, and Jiayi Zheng. From an odd arity signature to a Holant dichotomy, 2025. doi:10.48550/arXiv.2502.05597.

[bib.bib26] [26] Shuai Shao and Jin-Yi Cai. A dichotomy for real Boolean Holant problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1091–1102. IEEE, 2020. doi:10.1109/FOCS46700.2020.00105.

[bib.bib27] [27] Shuai Shao and Zhuxiao Tang. Eulerian orientations and Hadamard codes: A novel connection via counting. arXiv preprint, 2024. doi:10.48550/arXiv.2411.02612.

[bib.bib28] [28] Leslie G. Valiant. Accidental algorthims. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’06, pages 509–517. IEEE Computer Society, 2006. doi:10.1109/FOCS.2006.7.

[bib.bib29] [29] Leslie G Valiant. Holographic algorithms. SIAM Journal on Computing, 37(5):1565–1594, 2008. doi:10.1137/070682575.

[bib.bib30] [30] Peng Yang, Yuan Huang, and Zhiguo Fu. The computational complexity of Holant problems on 3-regular graphs. Theoretical Computer Science, 982:114256, 2024. doi:10.1016/j.tcs.2023.114256.

From an Odd Arity Signature to a Holant Dichotomy

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1 (Decomposition lemma).

Theorem 2 (Dichotomy for Holantodd).

2 Preliminaries

2.1 Definitions and notations

2.2 Frameworks of counting problems

Definition 3 (Holant problems).

Definition 4 (#⁢CSP).

Definition 5.

Lemma 6 ([5, Lemma 1.2]).

Lemma 7.

2.3 Fundamental methods

2.3.1 Signature factorization

Lemma 8 ([8, Lemma 2.13]).

2.3.2 Gadget construction and signature matrix

Lemma 9 ([9, Lemma 3.9]).

2.3.3 Holographic transformations and SLOCC

Theorem 10 ([29]).

Lemma 11.

Lemma 12 ([8]).

Lemma 13 ([19]).

2.3.4 Polynomial interpolation

Lemma 14.

2.4 Known dichotomies

2.4.1 #CSP and #CSP𝒅

Definition 15.

Definition 16.

Lemma 17.

Theorem 18 ([16, Theorem 3.1]).

Theorem 19 ([17]).

Theorem 20 ([9, Theorem 5.3]).

2.4.2 Holant𝒄

Definition 21.

Definition 22.

Theorem 23 ([3, Theorem 59]).

2.4.3 K-Holant

Definition 24.

Definition 25.

Theorem 26 ([23, 24]).

Corollary 27 ([24]).

Theorem 28 ([24]).

3 Main results

Theorem 29 (Decomposition lemma).

Theorem 30 (Dichotomy for Holantodd).

▶ Remark 31.

Lemma 32.

4 Decomposition lemma

Lemma 33 ([22, Lemma 3.1]).

Lemma 34 ([22, Lemma 3.2]).

Lemma 35 ([22, Corollary 3.3]).

▶ Remark 36.

Lemma 37.

Corollary 38.

Lemma 39.

5 Dichotomy for Holantodd

Lemma 40.

5.1 A dichotomy for Holant problems when 𝚫𝟎 is available

Lemma 41.

Lemma 42 ([6, Part of Lemma 2.40]).

Lemma 43 ([17, Lemma 5.2]).

Lemma 44 ([13]).

Lemma 45 ([13]).

Lemma 46 ([13]).

Lemma 47.

Lemma 48 ([2]).

Lemma 49 ([2]).

Lemma 50 ([2]).

Lemma 51.

Lemma 52.

Theorem 2 (Dichotomy for $\textup{{Holant}}^{\text{odd}}$ ).

Definition 4 ( $\#\textup{{CSP}}$ ).

2.4.1 #CSP and $\textup{{\#CSP}}_{d}$

2.4.2 $\textup{{Holant}}^{c}$

Theorem 30 (Dichotomy for $\textup{{Holant}}^{\text{odd}}$ ).

$\blacktriangleright$ Remark 31.

$\blacktriangleright$ Remark 36.

5 Dichotomy for $\textup{{Holant}}^{\text{odd}}$

5.1 A dichotomy for Holant problems when $\Delta_{0}$ is available