Complex-valued Holant with a non-trivial odd-arity signature is classified: every instance is either #P-hard or in FPNP.
The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The complexity classification of the Holant problem has remained unresolved for the past fifteen years. Counting complex-weighted Eulerian orientation problems, denoted as #EO, is regarded as one of the most significant challenges to the comprehensive complexity classification of the Holant problem. This article presents an $\text{FP}^\text{NP}$ vs. #P dichotomy for #EO, demonstrating that #EO defined by a signature set is either #P-hard or polynomial-time computable with a specific NP oracle. This result provides a comprehensive complexity classification for #EO, and potentially leads to a dichotomy for the Holant problem. Furthermore, we derive three additional dichotomies related to the Holant problem from the dichotomy for #EO.
fields
cs.CC 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
From an odd arity signature to a Holant dichotomy
Complex-valued Holant with a non-trivial odd-arity signature is classified: every instance is either #P-hard or in FPNP.