arXiv:2610.00081 · v2

A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems

首次提交 2026-09-06 23:50

版本更新 2026-11-06 23:13

雷达观测 2026-11-09 13:22

摘要

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.

作者备注：98 pages; proof and exposition revised, Lean repository linked