The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915257659686912 |
|---|---|
| author | Meng, Boning Wang, Juqiu Xia, Mingji |
| author_facet | Meng, Boning Wang, Juqiu Xia, Mingji |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_02012 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO Meng, Boning Wang, Juqiu Xia, Mingji Computational Complexity 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. |
| title | The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2502.02012 |