betaFeedback

WorksComputer Science

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

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(F))≅C2M(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)SO(3), providing an algebraic viewpoint for structural classification. This paper further identifies two fundamentally different regimes for the C2C_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 F\mathcal{F} satisfying M(\B(\mathcal{F}))\cong C_2, the problem Holant(F)\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.

Paper details

vlnc:W_pk7jc68n
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…