下载中心
会议室预定
电子邮箱
【06-25】知行融创论坛：From an odd arity signature to a Holant dichotomy
| 知行融创论坛-实验室月度学术交流 | |
| Speaker: | 郑加毅 |
| Time: | 2025年6月25日 |
| Venue: | 中国科学院软件园区5号楼三层 334报告厅 |
| Abstract: | Holant is an essential framework in the field of counting complexity. For over fifteen years, researchers have been clarifying the complexity classification for complex-valued Holant on the Boolean domain, a challenge that remains unresolved. In this article, we prove a complexity dichotomy for complex-valued Holant on Boolean domain when a non-trivial signature of odd arity exists. This dichotomy is based on the dichotomy for #EO, and consequently is an FP^NP vs. #P dichotomy as well, stating that each problem is either in FP^NP or #P-hard.
Furthermore, we establish a generalized version of the decomposition lemma for complex-valued Holant on Boolean domain. It asserts that each signature can be derived from its tensor product with other signatures, or conversely, the problem itself is in FP^NP. We believe that this result is a powerful method for building reductions in complex-valued Holant, as it is also employed as a pivotal technique in the proof of the aforementioned dichotomy in this article. |
| Download | From an odd arity signature to a Holant dichotomy |