Holant* Dichotomy on Domain Size 3:
A Geometric Perspective

Holant problems were introduced in [14] as a broad framework to study the computational complexity of counting problems. Counting CSP is a special case of Holant problems [18, 4, 3, 19, 13, 21, 8, 5]. In turn, counting CSP includes counting graph homomorphisms (GH), introduced by Lovász [26, 24], which is a special case with a single binary constraint function. Typical Holant problems include counting all matchings, counting perfect matchings #PM (including all weighted versions), counting cycle covers, counting edge colorings, and many other natural problems. It is strictly more expressive than GH; for example, it is known that #PM cannot be expressed in the framework of GH [22, 9].

The complexity classification program of counting problems is to classify as broad a class of problems as possible according to their inherent computational complexity within these frameworks. Let $ℱ$ be a set of (real or complex valued) constraint functions defined on some domain set $D$. It defines a Holant problem $\mathrm{Holant}(ℱ)$ as follows. An input consists of a graph $G=(V,E)$, where each $v\in V$ has an associated $𝐅\in ℱ$, with incident edges to $v$ labeled as input variables of $𝐅$. The output is the sum of products of evaluations of the constraint functions over all assignments over $D$ for the variables. The goal of the complexity classification of Holant problems is to classify the complexity of $\mathrm{Holant}(ℱ)$. A complexity dichotomy theorem for counting problems classifies every problem in a broad class of problems $ℱ$ to be either polynomial time solvable or #$𝖯$-hard.

There has been tremendous progress in the classification of counting GH and counting CSP [18, 19, 13, 3, 21, 8, 5, 20, 1, 23, 7]. Much progress was also made in the classification of Holant problems, particularly on the Boolean domain ($|D|=2$), i.e., when variables take 0-1 values (but constraint functions take arbitrary values, such as partition functions from statistical physics). This includes the dichotomy for all complex-valued symmetric constraint functions [10] and for all real-valued not necessarily symmetric constraint functions [27]. On the other hand, obtaining higher domain Holant dichotomy has been far more challenging. There is a huge increase in difficulty in proving dichotomy theorems for domain size $>2$, as already seen in decision CSP of domain size $3$, a major achievement by Bulatov [2]. Toward proving these dichotomies one often first considers restricted classes of Holant problems assuming some particular set of constraint functions are present. Two sets stand out: (1) the set of equality functions $ℰ𝒬$ of all arities (this is the class of all counting CSP problems) and (2) the set of all unary functions $𝒰$, i.e., functions of arity one. Indeed, #CSP($ℱ)=\mathrm{Holant}(ℱ\cup ℰ𝒬)$; i.e., counting CSP are the special case of Holant problems with $ℰ𝒬$ assumed to be present. In this paper we study (2): ${\mathrm{Holant}}_3^{\ast }(ℱ):={\mathrm{Holant}}_3(ℱ\cup 𝒰)$, for an arbitrary set $ℱ$ of symmetric real-valued constraint functions on domain size 3.

Previously there were only two significant Holant dichotomies on higher domains. One is for a single ternary constraint function that has a strong symmetry property called domain permutation invariance [11]. That work also solves a decades-old open problem of the complexity of counting edge colorings. The other is a dichotomy for ${\mathrm{Holant}}_3^{\ast }(f)$ where $f$ is a single symmetric complex-valued ternary constraint function on domain size 3 [15]. Extending this dichotomy to an arbitrary constraint function, or more ambitiously, to a set of constraint functions has been a goal for more than 10 years without much progress.

In this paper, we extend the result in [15] to an arbitrary set of real-valued symmetric constraint functions. In [25] an interesting observation was made that an exceptional form of complex-valued tractable constraint functions does not occur when the function is real-valued. By restricting ourselves to a set $ℱ$ of real-valued constraint functions, we can bypass a lot of difficulty associated with this exceptional form. Another major source of intricacy is related to the interaction of binary constraint functions with other constraint functions in $ℱ$. We introduce a new geometric perspective that provides a unifying principle in the formulation as well as a structural internal logic of what leads to tractability and what leads to #$𝖯$-hardness. After discovering some new tractable classes of functions aided by the geometric perspective, we are able to prove a ${\mathrm{Holant}}_3^{\ast }(ℱ)$ dichotomy. This dichotomy is dictated by the geometry of the tensor decomposition of constraint functions.

Suppose $𝐆$ is a binary constraint function and $𝐅$ is a tenary constraint function, with $𝐅={𝐮}^{\otimes 3}+{𝐯}^{\otimes 3}$ its tensor decomposition. One of the simplest constructions possible with $𝐆$ and $𝐅$ is to connect $𝐆$ at the three edges of $𝐅$; the resulting constraint function is ${𝐆}^{\otimes 3}𝐅$ which has tensor decomposition ${(\mathrm{𝐆𝐮})}^{\otimes 3}+{(\mathrm{𝐆𝐯})}^{\otimes 3}$. We see that this gadget construction plays nicely with the tensor decomposition. Generalizing this idea, suppose $ℬ$ is a set of binary constraint functions and $𝒯$ is a set of ternary constraint functions. Let $⟨ℬ⟩$ be the monoid generated by $ℬ$. We may consider the orbit $𝒪$ of $𝒯$ under the monoid action of $⟨ℬ⟩$, such that $𝐆\in ⟨ℬ⟩$ acts on $𝐅\in 𝒯$ by $𝐆:𝐅\mapsto {𝐆}^{\otimes 3}𝐅$. Although the constraint functions in $𝒪$ are the results of a very simple gadget construction, we show that $𝒪$ contains sufficient information about the interaction of binary constraint functions and other constraint functions, and the simplicity allows us to analyze it by considering the geometry of the vectors of the tensor decomposition of the constraint functions in $𝒪$.

Compared to the Boolean domain dichotomy theorem, stated in explicit recurrences on the values of the signatures (see Theorem 2.12 in [6]) the dichotomy theorem (Theorem 3.1) we wish to prove has a more non-explicit form, which is also more conceptual. This is informed by the geometric perspective, but it also causes some difficulty in its proof, when we try to extend to a set of constraint functions of arbitrary arities. We introduce a new technique to overcome this difficulty. First (and this is quite a surprise), it turns out that a dichotomy of two constraint functions of arity $3$ is easier to state and prove than the dichotomy of one binary and one ternary constraint functions. Also they can be proven independently of each other. This is a departure from all previous proofs of dichotomy theorems in this area. Second, using the unary constraint functions available in ${\mathrm{Holant}}^{\ast }$, any symmetric constraint function $𝐅$ of arity $4$ defines a linear transformation from ${ℝ}^3$ to the space of symmetric constraint functions of arity $3$, which corresponds to the ternary constraint functions constructible by connecting a unary function to $𝐅$. In particular, the image of this map, $ℱ$, is a linear subspace. In particular, the image $ℱ$ of this map is a linear subspace. Considering the space $ℱ$ instead of specific sub-functions allows us to bypass the difficulty from the non-explicit form of the dichotomy statement, which is in terms of tensor decompositions up to an orthogonal transformation. We show that a dichotomy of two ternary constraint functions and the fact that $ℱ$ is closed under linear combinations imply that $ℱ$ must be of a very special form for ${\mathrm{Holant}}_3^{\ast }(ℱ)$ to be tractable, which in turn implies that $𝐅$ must possess a certain regularity.

While the tractability criterion in Theorem 3.1 is stated in a conceptual and succinct way, the tractable cases are actually quite rich and varied. We present here specific examples of new tractable cases. Denote the domain by $D=\{𝖡,𝖦,𝖱\}$. We use the notation in Figure 1 to denote a symmetric ternary constraint function on domain $D$.

Consider the four constraint functions ${𝐅}_1,{𝐆}_1,{𝐇}_1,{𝐁}_1$ in Figure 2.

It is not obvious that ${\mathrm{Holant}}_3^{\ast }({𝐅}_1,{𝐆}_1,{𝐇}_1,{𝐁}_1)$ is polynomial-time computable.

We apply the orthogonal transform which transforms ${𝐅}_1,{𝐆}_1$ and ${𝐇}_1$ to be supported on ${\{𝖡,𝖦\}}^{\ast },{\{𝖡,𝖱\}}^{\ast },{\{𝖦,𝖱\}}^{\ast }$ respectively, Their tensor decompositions have a revealing structure. Ignoring the scalar constants, we have¹¹1We use $𝔦$ to denote the imaginary unit. Complex numbers do appear, even though the signatures are all real valued. This is similar to eigenvalues.

The vectors in tensor decompositions show that geometrically, ${𝐅}_1^{\prime }$, ${𝐆}_1^{\prime }$, and ${𝐇}_1^{\prime }$ are associated with three coordinate planes. The function ${𝐁}_1^{\prime }=T^{\otimes 2}{𝐁}_1$ written in matrix form is , where the $(i,j)$ entry is the function value ${𝐁}_1^{\prime }(i,j)$, for $i,j$ in the new domain set. Applying Theorem 3.1 we can conclude that $\{{𝐅}_1,{𝐆}_1,{𝐇}_1,{𝐁}_1\}$ is in tractable class $ℰ$.

For the second example we apply the orthogonal transform to the constraint functions in Figure 3.

and $T^{\otimes 3}{𝐇}_2$ and $T^{\otimes 3}{𝐁}_2$ can be written in matrix form and respectively, up to scalar constants. Applying Theorem 3.1 we can conclude that $\{{𝐅}_2,{𝐆}_2,{𝐇}_2,{𝐁}_2\}$ is in tractable class $𝒟$.

Our new algorithm also solves some natural problems. Consider the following problem. For $n\in \mathbb{N}$, $i\ne j\in \{𝖡,𝖦,𝖱\}$, and any $a,b\in ℝ$, let ${\mathrm{𝖯𝖠𝖱𝖨𝖳𝖸}}_{a,b}^{n,i,j}:{\{𝖡,𝖦,𝖱\}}^n\to ℝ$ be the function

Let ${(\ne )}_{pq;r}:{\{𝖡,𝖦,𝖱\}}^2\to \{0,1\}$ for distinct $p,q,r\in \{𝖡,𝖦,𝖱\}$ be the function

Let $ℱ=\{{\mathrm{𝖯𝖠𝖱𝖨𝖳𝖸}}_{a,b}^{n,i,j}:i\ne j\in \{𝖡,𝖦,𝖱\},a,b\in ℝ\}\cup \{{(\ne )}_{pq;r}:\text{distinct }p,q,r\in \{𝖡,𝖦,𝖱\}\}.$ There is a related constraint satisfaction decision problem, where

and we ask if an ${ℱ}^b$ signature grid has a nonzero assignment. It is not even immediately obvious whether this decision problem is solvable in polynomial time. Theorem 3.1 tells us that $ℱ$ is in class $ℰ$ and thus ${\mathrm{Holant}}_3^{\ast }(ℱ)$ is computable in polynomial time, which implies that the decision problem is also solvable in polynomial time.

Let $ℱ$ be a set of nondegenerate, real-valued, symmetric signatures over domain $\{𝖡,𝖦,𝖱\}$.

In classes $𝒞$, $𝒟$, and $ℰ$, we refer to the ${\mathrm{Holant}}_2^{\ast }$ tractability. By the Boolean domain dichotomy, it is necessary that those ${\mathrm{Holant}}_2^{\ast }$ problems are tractable.

In case (b) of class $ℰ$, it seems like we may need to use the asymmetric ${\mathrm{Holant}}_2^{\ast }$ dichotomy (which is known [16]), because while the signatures in $ℛ$ are symmetric, $⟨ℛ⟩$ may contain asymmetric signatures. We claim that is not necessary. Let $𝐆\in O_h$. If ${𝐆}^{\ast \to \{i,j\}}$ is nondegenerate and asymmetric, then . We can deduce that ${𝐆}^{\ast \to \{i,j\}}$ is universally compatible, i.e., when appended to any ${\mathrm{Holant}}_2^{\ast }$ tractable class results in a tractable set, without referring to any asymmetric ${\mathrm{Holant}}_2^{\ast }$ dichotomy. For type $\mathrm{I}(a,b)$ (see Definitions A.1 and A.2), we see that . The first matrix in the symmetric signature notation is $[b,-2a,-b]$, which satisfies the recurrence $a\cdot b+b(-2a)=a\cdot (-b)$. The second matrix in the symmetric signature notation is $[2a,b,-2a]$, which is the other specified form. For type $\mathrm{II}$, we see that , and $[1,0,-1]$ and $[0,1,0]$ are type $\mathrm{II}$.

This is not a coincidence. We may view the ${\mathrm{Holant}}_2^{\ast }$ dichotomy in a geometric way. Consider the tractable type $\mathrm{I}(a,b)$. There are two norm $1$ orthogonal vectors $𝐮,𝐯\in {ℝ}^2$ such that any signature of arity $\ge 3$ of type $\mathrm{I}(a,b)$ is of the form $c{𝐮}^{\otimes n}+d{𝐯}^{\otimes n}$. We may represent type $\mathrm{I}(a,b)$ signatures of arity $\ge 3$ by two orthogonal lines in the ${ℝ}^2$ plane. Consider the gadget construction of connecting a binary signature $𝐆$ to all of the edges of a signature. In the tensor decomposition form, we have ${𝐆}^{\otimes n}(c{𝐮}^{\otimes n}+d{𝐯}^{\otimes n})=c{(\mathrm{𝐆𝐮})}^{\otimes n}+d{(\mathrm{𝐆𝐯})}^{\otimes n}$. For the binary signatures, we can check that the tractable signatures correspond to the linear transformations that fix the union of the two orthogonal lines as a set. This is easily verified for the case of type $\mathrm{I}(0,1)$, when $𝐮={𝐞}_1$ and $𝐯={𝐞}_2$, since $[\ast ,0,\ast ]$ signature corresponds to scaling ${𝐞}_1$ and ${𝐞}_2$, while $[0,\ast ,0]$ signature corresponds to reflection along $x=y$ line, and similarly for other type $I(a,b)$. The asymmetric signature above is a $\pi /2$ rotation, which fixes any pair of orthogonal lines, so it is tractable with all $\mathrm{I}(a,b)$ types.

The tractable type $\mathrm{II}$ may be viewed as a circle in the ${ℝ}^2$ plane. The justification is that any type $\mathrm{II}$ signature can be written as ${(𝐮+𝔦𝐯)}^{\otimes n}+{(𝐮-𝔦𝐯)}^{\otimes n}$ for two orthogonal $𝐮,𝐯\in {ℝ}^2$ of the same norm, and all such signatures can be constructed from one type $\mathrm{II}$ signature. The set of linear transformations that fix the circle is the orthogonal group $O(2)$. We see that up to a scalar factor, the signature $[x,y,-x]$ corresponds to a reflection matrix and the signature $[x,0,x]$ to the identity. Since any rotation can be written as a product of two reflections, they are also compatible with type $\mathrm{II}$ signatures.

A similar analogy can be made for domain $3$ signatures as well, since the tensor decomposition forms in Theorem 2.3 are also about orthogonality of the vectors. Similar to the Boolean domain tractable signatures, a tractable domain $3$ signature also can be represented as a set of vectors in the three dimensional space. For instance, let ${𝐮}_1^{\otimes 3}+{𝐮}_2^{\otimes 3}$, ${𝐯}_1^{\otimes 3}+{𝐯}_2^{\otimes 3}$ and ${𝐰}_1^{\otimes 3}+{𝐰}_2^{\otimes 3}$, be three signatures. The idea is depicted in Figure 4, and this intuition is formalized in Lemma 5.3. Class $𝒞$ says that the signatures of arity $3$ or higher must live in some plane, and we can assume it is the $xy$-plane after an orthogonal transformation. The compatible binary signatures are those fixing the $xy$-plane ($\mathrm{𝖡𝖦}|𝖱$) or a degenerate transformation on the $xy$-plane. The class $𝒟$ says that the signatures of arity $3$ or higher are formed by the $xy$-plane and the $z$-axis. The compatible binary signatures, after the same orthogonal transformation, are those fixing the $xy$-plane and $z$-axis line ($\mathrm{𝖡𝖦}|𝖱$) or mapping between the $xy$-plane and the $z$-axis (${\mathrm{𝖲𝗐𝖺𝗉}}_{\mathrm{𝖡𝖦};𝖱}$). The class $ℰ$ says that the signatures of arity $3$ or higher must live in one of $xy$-plane, $yz$-plane, or $xz$-plane. The compatible binary signatures are those permuting the three planes without stretching. Such transformations are precisely the group $O_h$.

In this section, we prove tractability by giving a polynomial time algorithm for each of the classes in Theorem 3.1. By Corollary 2.2, ${\mathrm{Holant}}_3^{\ast }(ℱ)$ is tractable if and only if ${\mathrm{Holant}}_3^{\ast }(Tℱ)$ is tractable. Also, we may always assume that the given signature grid is connected, as the Holant value of any signature grid is the product over connected components.

Classes $𝒜$ and $ℬ$ are tractable by standard arguments. If every signature in $ℱ$ has arity $\le 2$ (class $𝒜$), then, the graph of the signature grid $\mathrm{\Omega }$ is a disjoint union of paths and cycles. By matrix multiplication, we can compute the Holant value for a path. The Holant value for a cycle is obtained by taking the trace of a path.

Suppose $Tℱ\subseteq ℰ$ for an orthogonal $T$ (class $ℬ$). Let $\mathrm{\Omega }$ be a $Tℱ$ signature grid and $e$ any edge. For any $𝖡,𝖦,𝖱$ assignment to $e$, the assignment must propagate uniquely to all edges, which implies that there are at most three assignments to the whole grid that can result in a nonzero Holant value.

After a dichotomy of a single ternary signature [15], a natural next step is proving a dichotomy of a pair of ternary and binary signatures (as binary signatures are the “simplest” signatures after unary signatures), and use it to prove further theorems. However, for domain size 3 in the Holant setting, binary signatures actually allow nontrivial, and somewhat unanticipated, interactions with other signatures. Also, it turns out that a dichotomy for a pair of binary and ternary signatures, while certainly needed on its own, is not easily applicable for showing further dichotomies. We circumvent this difficulty by proving a dichotomy of a pair of ternary signatures directly.

We describe the logical dependency of our proof in Figure 7. We start with the known dichotomy, Theorem 2.3, of a single ternary signature. We use it to show the dichotomy of a pair of ternary and binary signatures and a pair of ternary signatures. These two proofs can be found in the full version [12] and we note that they are independent of each other. To arrive at a dichotomy of a set of signatures, we also need to show a dichotomy for any single signature of arbitrary arity $n\ge 4$, which we show in Section 6. The remaining proof leading to a dichotomy of a set of signatures can be found in the full version [12].

The main intuition behind the proof of hardness is the geometry of the vectors in a tensor decomposition of a signature.

We always start with a canonical form of a signature (after a suitable orthogonal transformation), for example, $𝐅={𝐞}_1^{\otimes 3}+{𝐞}_2^{\otimes 3}$. $𝐅$ can realize $({=}_{\mathrm{𝖡𝖦}})$ and take domain restriction to $\{𝖡,𝖦\}$. If the other signature is $𝐆={𝐮}^{\otimes 3}+{𝐯}^{\otimes 3}$ for orthogonal $𝐮,𝐯\in {ℝ}^3$, the domain restriction is ${𝐆}^{\ast \to \{𝖡,𝖦\}}={({\mathrm{proj}}_{xy}𝐮)}^{\otimes 3}+{({\mathrm{proj}}_{xy}𝐯)}^{\otimes 3}$. Essentially, most of the arguments boil down to showing that the angle between ${\mathrm{proj}}_{xy}𝐮$ and ${\mathrm{proj}}_{xy}𝐯$ must be $\pi /2$ (with one exception), otherwise, ${𝐆}^{\ast \to \{𝖡,𝖦\}}$ is #$𝖯$-hard by the Boolean domain dichotomy. The other tractable possibility is when ${\mathrm{proj}}_{xy}𝐮\sim {\mathrm{proj}}_{xy}𝐯$, which can only happen if the plane that contains $𝐮$ and $𝐯$ contains the $z$-axis, which corresponds to the case when ${𝐆}^{\ast \to \{𝖡,𝖦\}}$ is degenerate.

Using this idea, we can prove the dichotomy of ${\mathrm{Holant}}_3^{\ast }(𝐅,𝐆)$ in which $𝐅,𝐆$ are ternary signatures. The individual statements can be found in the full version [12]. We can see that the statements are more complex when signatures are of rank $2$. We define a notion of a plane of a rank $2$ signature, which formalizes the idea behind Figure 4 and allows us to express the dichotomy succinctly. A rank 2 signature of type $𝔄$ or type $𝔅$ of Theorem 2.3 has a symmetric tensor decomposition such that the two vectors occurring inside it are orthogonal, i.e. ${𝐯}_1^{\otimes 3}+{𝐯}_2^{\otimes 3}$ or ${({𝐯}_1+𝔦{𝐯}_2)}^{\otimes 3}+{({𝐯}_1-𝔦{𝐯}_2)}^{\otimes 3}$. The two vectors are unique up to a scalar, so the plane of a signature $𝐅$, denoted by $P_{𝐅}=\mathrm{span}({𝐯}_1,{𝐯}_2)$, is well defined.

Note that $𝐅$ is EBD if and only if $P_{𝐅}$ is one of the coordinate planes, i.e. $xy$-plane, $yz$-plane or $xz$-plane. We will say that two planes are orthogonal if their normal vectors are orthogonal. This notion is well defined because a normal vector to a plane in $3$ dimensional space is unique up to a scalar. The following proposition can be shown with elementary linear algebra.

The next lemma encapsulates the essence of the dichotomy theorems of two ternary signatures of rank $2$, and extends it to an arbitrary set of rank $2$ ternary signatures.

The idea of viewing binary signatures as transformation on the signatures is naturally captured by the following construction. Let $𝒯$ be a set of ternary signatures and $ℬ$ be a set of binary signatures. Let $ℱ=𝒯\cup ℬ$. Let $⟨ℬ⟩$ be the monoid generated by $ℬ$ under multiplication. We define $𝒪$ to be

Combinatorially, $𝒪$ is the set of all gadgets constructible from connecting the same chain of binary signatures to the three edges of a ternary signature, ${({𝐆}_1{𝐆}_2\mathrm{\cdots }{𝐆}_k)}^{\otimes 3}𝐅$ for some ${𝐆}_i\in ℬ$ and $𝐅\in 𝒯$. It can also be viewed as the orbit (ignoring degenerate signatures) of $𝒯$ under the monoid action of $⟨ℬ⟩$, where the action is defined by $𝐆:𝐅\mapsto {𝐆}^{\otimes 3}𝐅$ for $𝐆\in ⟨ℬ⟩$ and $𝐅\in 𝒯$. Note that $𝒢$ is a set of symmetric ternary signatures, and if $𝐆\in ℬ$ and $𝐅\in 𝒪$, then ${𝐆}^{\otimes 3}𝐅\in 𝒪$ as well.

To complete the proof of the dichotomy of ${\mathrm{Holant}}_3^{\ast }(ℱ)$, we use Lemma 5.3 on ${\mathrm{Holant}}_3^{\ast }(𝒪)$ to analyze $ℬ$. The details can be found in the full version [12].

In this section, we prove a dichotomy of ${\mathrm{Holant}}_3^{\ast }(𝐅)$ for an $𝐅$ of arbitrary arity $n$. The case $n\le 3$ was proved in [15]. Let $n\ge 4$. Similar to the Boolean domain case, it is natural to expect that higher arity tractable signatures also have the same tensor decomposition form, i.e. $a{𝐞}_1^{\otimes n}+b{𝐞}_2^{\otimes n}+c{𝐞}_3^{\otimes n}$ or ${𝜷}^{\otimes n}+{\overline{𝜷}}^{\otimes n}+\lambda {𝐞}_3^{\otimes n}$ for $𝜷=(1,𝔦,0)$ after some orthogonal transformation. We show that indeed this is the case.

The proof is an induction on the arity. Assume ${\mathrm{Holant}}_3^{\ast }(𝐅)$ is not #P-hard. First, we show that $𝐅$ of arity $4$ must be of a suitable form, using the dichotomy of two ternary signatures. Then we show that arity $4$ signatures must have a tensor decomposition of at most $3$ linearly independent vectors. Then we argue that the dichotomy of two arity $4$ signatures must take essentially the same form as the dichotomy of two ternary signatures. Finally, we generalize the proof to higher arities. The logical dependency is visualized in Figure 7.