From Holant To #CSP And Back: Dichotomy For Holant$^c$ Problems

Jin-yi Cai, Sangxia Huang, Pinyan Lu

Abstract

This paper establishes a complete complexity dichotomy for Holant$^c$ problems, proving that every such problem is either solvable in polynomial time (P) or is #P-hard. By leveraging holographic reductions, the authors bridge the gap between Counting Constraint Satisfaction Problems (#CSP) and the Holant framework. The results demonstrate that the true nature of these counting problems is revealed when investigated in the complex domain $\mathbb{C}$, where holographic transformations provide a unified language for tractability.

Introduction

In computational complexity theory, counting problems—such as determining the number of perfect matchings in a graph—are categorized into frameworks like #CSP, weighted H-colorings, and Holant problems. While #CSP is well-studied, the Holant framework offers a more expressive environment for problems that #CSP cannot easily capture. This paper focuses on Holant$^c$ problems, a class that allows for the inclusion of constant unary functions 0 and 1, effectively permitting the "fixing" of certain variables or edges to specific values. Prior to this work, a complete classification for these problems over the complex numbers $\mathbb{C}$ was missing.

Methodology

The authors utilize several advanced algebraic and combinatorial techniques to map the complexity landscape of these problems.

Holographic Reductions and Gadgets

The primary tool is the holographic reduction, which uses linear transformations to map one counting problem to another while preserving the total sum (the "Holant"). This allows the authors to demonstrate that seemingly distinct problems are equivalent under a change of basis. To simulate specific functions or "unary gates," the authors employ interpolation, building complex gadgets within the graph structure.

A basic gadget construction used in holographic reductions and interpolation to simulate specific functions.

These gadgets are essential for establishing hardness by reducing known #P-hard problems to the cases under study. More sophisticated recursive constructions are often required to achieve the necessary simulations for the dichotomy proof.

A complex recursive gadget used to establish hardness through interpolation in the Holant framework.

The "Back and Forth" Strategy

Unlike traditional approaches that solely reduce #CSP to Holant, this paper employs a bidirectional strategy. The authors use a known dichotomy for #CSP to derive results for a specific Holant class, which in turn facilitates further developments in Holant theory. This "back and forth" approach reveals a deep mathematical unity between the frameworks.

Key Insights

  • The Power of the Complex Domain: The authors argue that the fundamental properties of counting problems are best understood in the complex domain $\mathbb{C}$. Even for real-valued problems, the most direct proofs often involve complex-valued transformations.
  • Holographic Unity: Tractable cases are often "accidental" and their simplicity can only be naturally expressed through holographic transformations.
  • Correcting Conjectures: The study identified previously unknown tractable cases, such as Holant^c([1, 0, i, 0]), correcting earlier incomplete conjectures about the boundary between P and #P-hardness.

Key Results

The research culminates in three major dichotomy theorems:

  1. Ternary Dichotomy: A complete classification for any single symmetric ternary function.
  2. Bipartite Holant Dichotomy: A general dichotomy for Holant problems on bipartite graphs, serving as a bridge to #CSP.
  3. The Holant$^c$ Dichotomy: The main result provides a complete classification for the Holant$^c$ class over any set of symmetric complex-valued functions.

Conclusion and Future Work

The authors prove that every Holant$^c$ problem is either in P or #P-hard, assuming P $\neq$ #P. While this work provides a definitive classification for symmetric functions in the boolean domain, extending these results to non-symmetric functions and larger domain sizes remains a significant challenge for future research.

Summary updated

Abstract

We explore the intricate interdependent relationship among counting problems, considered from three frameworks for such problems: Holant Problems, counting CSP and weighted H-colorings. We consider these problems for general complex valued functions that take boolean inputs. We show that results from one framework can be used to derive results in another, and this happens in both directions. Holographic reductions discover an underlying unity, which is only revealed when these counting problems are investigated in the complex domain $\mathbb{C}$. We prove three complexity dichotomy theorems, leading to a general theorem for Holant$^c$ problems. This is the natural class of Holant problems where one can assign constants 0 or 1. More specifically, given any signature grid on $G=(V,E)$ over a set ${\mathscr F}$ of symmetric functions, we completely classify the complexity to be in P or #P-hard, according to ${\mathscr F}$, of \[\sum_{σ: E \rightarrow \{0,1\}} \prod_{v\in V} f_v(σ\mid_{E(v)}),\] where $f_v \in {\mathscr F} \cup \{{\bf 0}, {\bf 1}\}$ ({\bf 0}, {\bf 1} are the unary constant 0, 1 functions). Not only is holographic reduction the main tool, but also the final dichotomy can be only naturally stated in the language of holographic transformations. The proof goes through another dichotomy theorem on boolean complex weighted #CSP.
BibTeX
@article{cai2012from,
  author = {Jin-yi Cai and Sangxia Huang and Pinyan Lu},
  title = {{From Holant To \#CSP And Back: Dichotomy For Holant$^c$ Problems}},
  journal = {Algorithmica},
  year = {2012},
  doi = {10.1007/s00453-012-9626-6},
}
Figure