সংরক্ষণ করুন:
| প্রধান লেখক: | , , |
|---|---|
| বিন্যাস: | Preprint |
| প্রকাশিত: |
2025
|
| বিষয়গুলি: | |
| অনলাইন ব্যবহার করুন: | https://arxiv.org/abs/2502.02012 |
| ট্যাগগুলো: |
ট্যাগ যুক্ত করুন
কোনো ট্যাগ নেই, প্রথমজন হিসাবে ট্যাগ করুন!
|
সূচিপত্রের সারণি:
- 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.