CS Paper Radar

A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems

Chenghua Liu, Boning Meng, Juqiu Wang

cs.CC ·submitted 2026-09-06 15:50 UTC · v2
theory

Abstract

A Boolean Holant problem evaluates a graph partition function specified by local signatures at its vertices. We prove a complexity dichotomy for arbitrary finite sets of algebraic complex-valued signatures on general graphs: an explicit, decidable criterion characterizes the polynomial-time cases, and every remaining case is $\#\mathsf{P}$-hard under polynomial-time Turing reductions. The proof resolves the all-even case by constructing signatures with nonzero endpoints and all remaining support on the central layer, then classifying them according to half their arity. Binary transfer groups and matching-product reconstruction provide the main tools in the small- and large-height cases, respectively.

Comment
98 pages; proof and exposition revised, Lean repository linked

Closest papers

Nearest neighbours by meaning across the whole index.

A Dichotomy for Complex Boolean Holant with Binary Disequality

cs.CC ·2026-08-31 ·Chenghua Liu, Boning Meng
similarity 0.83
Abstract · 242 pages; proof and exposition revised, corrections made, Lean repository linked

We classify Boolean Holant problems with a supplied binary disequality signature and an arbitrary fixed finite set of algebraic complex-valued signatures. Each problem is polynomial-time computable or $\#\mathsf{P}$-hard, and the tractability criterion is decidable. The proof combines arity reduction with the growth of the available binary transfer group and uses stable pairs to recover the structure of higher-arity signatures. We also prove a dichotomy for the disequality-edge model when the signature set contains an endpoint-nondegenerate irreducible eight-vertex signature, resolving the corresponding arity-four cases in the main proof.

0.33

A Dichotomy for Cubic Bipartite Holant Problems with Complex Algebraic Weights

cs.CC ·2026-09-27 ·Yin Liu
similarity 0.73
Abstract · 87 pages. Supplementary polynomial certificates and verification code included. Corrected author metadata; manuscript unchanged

We classify the exact evaluation of $\operatorname{Holant}(f\mid=_3)$ for every fixed complex algebraic symmetric Boolean ternary signature $f$. An input is a cubic bipartite multigraph: every vertex on one side carries $f$, every vertex on the other side carries ternary equality, and no auxiliary signatures are freely available. The tractable signatures are precisely rank-one tensors, generalized equalities, and equality-preserving cube-root diagonal transformations of six affine signatures, together with nonzero scalings and reversal. Every other signature gives a $\#\mathrm{P}$-hard problem under polynomial-time Turing reductions. We also identify the exact real intersection: it consists of the same tractable families as in the rational classification, with real algebraic parameters. The proof preserves degree exactly three on both sides of every oracle instance. A rank-one matrix extracted by interpolation supplies one unary signature only after its unused factor has been absorbed in triples. Over the complex numbers this absorption has three exceptional projective directions. We combine this constraint with projective matrix-group orbits, explicit ternary replacements, and an exhaustive treatment of finite projective orders. The cases of orders three and five include exact polynomial certificates; the certificate identities and a rational-arithmetic verifier are supplied as supplementary material.

0.13

The Computational Complexity of Holant Problems on 4-regular Graphs from the Stable Subgroup Sequence of $SL(2,\mathbb{C})$

cs.CC ·2026-09-10 ·Yuan Huang, Zhiguo Fu
theory similarity 0.72
Abstract

The Holant framework provides a general setting for studying counting problems and includes graph homomorphisms (\#GH) and counting constraint satisfaction problems (\#CSP) as special cases. Over the past twenty years, a series of computational complexity dichotomies have been established for Holant problems, but the classification for complex-valued signatures is still open. The main obstacle is the case in which all signatures have even arity. In this paper, we establish a dichotomy for Holant problems with a complex-valued 4-ary signature, which is a key base case for the full classification of Holant problems. We present a new strategy by introducing Schur's theorem, the classification of finite subgroups of $\mathrm{SL}(2,\mathbb{C})$ and stable subgroup sequences into the proof. These new techniques are of independent interest.

0.15

A Dichotomy for Boolean Complex Holant Problems with Conjugate-Closed Signature Sets

cs.CC ·2026-09-11 ·Jincheng Guan, Shuai Shao, Zhuxiao Tang
theory similarity 0.70
Abstract · 96 pages, 3 figures

We study Boolean Holant problems with complex-valued signature sets closed under conjugation. Such sets arise naturally in tensor-network expressions for classical strong simulation of quantum circuits. We prove a complexity dichotomy for such problems with an explicit tractability criterion. This extends the dichotomy for real-valued Holant problems, with the same four tractability conditions. Our proofs use Xia's projective binary group framework and quantum entanglement theory. The conjugate closure assumption precisely makes $k$-uniformity, directly applicable to the classification of Holant problems, by realizing reduced density matrices via Holant gadgets. We also use the classification of absolutely maximally entangled states to resolve a particular $6$-ary obstruction in our inductive proof of the \#P-hardness.

0.27

From a finite subgroup of $SO(3)$:$C_2$ leads to a Holant dichotomy

cs.CC cs.CLcs.DM ·2026-11-18 ·Yuxuan Zhou
theory similarity 0.65
Abstract

Counting complexity within the Holant framework has been extensively studied through complexity dichotomy theorems. While substantial progress has been achieved for various restricted settings, the general complex-valued even-arity case without auxiliary unary signatures remains largely open. This paper studies a fundamental case in this program where the binary signatures induce a group structure satisfying \(M(B(\mathcal{F}))\cong C_2\). It is observed that projective equivalence classes of binary signature matrices naturally embed into finite subgroups of \(SO(3)\), providing an algebraic viewpoint for structural classification. This paper further identifies two fundamentally different regimes for the \(C_2\) case, namely the normal and isotropic cases, and analyzes their complexity behavior separately. Combining gadget constructions, decomposition techniques, interpolation arguments, and a realnumberization approach that transforms the complex-valued setting into an equivalent real-structured framework, this paper establishes a complete dichotomy theorem: for every even-arity signature set \(\mathcal{F}\) satisfying \(M(\B(\mathcal{F}))\cong C_2\), the problem \(\mathrm{Holant}(\mathcal{F})\) is either polynomial-time computable or \#P-hard. A Pauli-basis representation for signatures is further introduced as an algebraically natural language for organizing realizable signatures and revealing structural relations that are less transparent in the standard basis.

0.24

The Complexity of Boolean Connectivity Problem of $k$-Horn Formulas

cs.CC cs.DS ·2026-08-20 ·Takashi Horiyama, Shoon Mineyoshi, Yuto Okura, Kazuhisa Seto, Junichi Teruyama
theory similarity 0.64
Abstract

The Boolean connectivity problem asks whether the set of satisfying assignments of a given Boolean formula forms a connected subgraph in the $n$-dimensional hypercube. This problem is known to be $\mathsf{coNP}$-complete, even when restricted to $k$-Horn formulas for $k \geq 3$, as shown by Makino, Tamaki, and Yamamoto. In this paper, we further investigate the computational complexity of {\sc Conn $k$-Horn}, the Boolean connectivity problem for $k$-Horn formulas. We provide algorithmic and hardness results for {\sc Conn $k$-Horn}. On the algorithmic side, we first present an exact exponential-time algorithm for arbitrary $k$ without any structural restrictions. Our algorithm builds on the deterministic PPZ algorithm proposed by Paturi, Pudlák, and Zane. It runs in $O^*(2^{(1 - 1/2k)n})$ time and polynomial space, achieving an exponential improvement over the previously known algorithm for the Boolean connectivity problem of $k$-CNF formulas, shown by Makino, Tamaki, and Yamamoto. We next give two polynomial-time algorithms for arbitrary $k$ under the following two restrictions: (i) each variable appears at most twice, and (ii) each clause has length exactly $k$ and each variable appears at most $k$ times. On the hardness side, we prove that {\sc Conn $3$-Horn} remains $\mathsf{coNP}$-complete even when each variable appears exactly three times.

0.26

Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem

cs.DS math.CO ·2026-08-31 ·Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani, Soheil Mohammadkhani
theory similarity 0.64
Abstract

We give the first polynomial-time algorithm, after half a century, for the celebrated Győri-Lovász theorem, which resolved a conjecture of Frank (1975). The theorem, one of the simplest existential theorems to explain, states that every $k$-connected graph can be partitioned into $k$ disjoint connected subgraphs of arbitrary prescribed positive sizes. This is a fundamental structural result with broad applications, such as flexible allocation of connected subnetworks of prescribed sizes in sufficiently connected cloud infrastructures. While Lovász (1977) gave a highly non-constructive proof for a stronger directed version using algebraic topology, Győri's original constructive proof (1976) requires exponential time. Despite more than 50 years of effort, no polynomial-time algorithm was known even for $k>4$. Determining the computational complexity of the Győri-Lovász theorem---whether it admits even a sub-exponential-time algorithm or is computationally hard (in particular, PLS-complete or PPAD)---has remained one of the central open problems in algorithmic graph theory. In this paper, we finally resolve this long-standing problem by a fundamentally new proof of the existential theorem via introducing the novel concept of \emph{flow-essential assignment}, which genuinely marries matching and cut structures and yields the first polynomial-time constructive algorithm for the Győri-Lovász theorem. In fact, we obtain a polynomial-time algorithm for Lovász's stronger directed version, whose proof was non-constructive even for DAGs; for DAGs, we further obtain a near-linear-time algorithm. We also develop polynomial-time algorithms for weighted generalizations where the seminal work of Chen, Kleinberg, Lovász, Rajaraman, Sundaram, and Vetta (JACM'07) on confluent flows established only existential non-constructive results.

0.37

Lettericity Is NP-Complete

cs.CC cs.DM ·2026-09-23 ·Henning Fernau, Samuel German, Kevin Mann, Nils Morawietz
theory similarity 0.63
Abstract · After we first posted this paper on arXiv, Vatter posted a proof that Lettericity is NP-complete which he obtained independently of ours (ar…

The lettericity of a graph $G$ is the smallest size of a set $Σ$ such that there exist $w_1, \ldots, w_{|V(G)|} \in Σ$ and a so-called decoder $D \subseteq Σ^2$ for which $G$ is isomorphic to the letter graph $(\{1, \ldots, |V(G)|\}, \{ij : 1 \le i < j \le |V(G)|, w_iw_j \in D\})$. It took around two decades of the study of lettericity for, in the simpler case of paths, a closed-form expression for its lettericity to be derived; this suggests that the question of whether the lettericity of an arbitrary graph can be computed in polynomial time is nontrivial. Indeed, this question has been raised repeatedly as an open problem in recent literature. We solve this problem by showing that the lettericity problem on arbitrary graphs is NP-complete. We also show that each of the natural ways in which a single part of a structure $(Σ, w_1, \ldots, w_{|V(G)|}, D)$ witnessing the lettericity could be constrained corresponds to an NP-complete problem, which resolves an additional three open problems from the literature; in particular, we show that the coloring extension, word extension, and decoder extension problems are NP-complete. Additionally, we use the reduction in the NP-completeness proof to give a lower bound on algorithms for lettericity under the Exponential Time Hypothesis (ETH): unless the ETH is false, there cannot exist a deterministic algorithm to decide whether the lettericity of an $n$-vertex graph is at most $k$ in time $2^{o(n)}$, even when $n = 6k$. Finally, we complement the known result that Lettericity is fixed-parameter tractable when parameterized by the standard parameter $k$ by providing a fixed-parameter algorithm with respect to the dual parameterization by $n-k$ running in $2^{\mathcal{O}((n-k)^2)} + \mathcal{O}(n)$ time.

0.40