软件所计数复杂性研究连中三元

中国科学院软件研究所，关于计数问题集合的复杂性刻画与分类的研究工作，三篇相关论文“The FP^NP versus #P dichotomy for #EO”、“P-time algorithms for typical #EO problems”、“From an odd arity signature to a Holant dichotomy”，先后被2025年三个理论计算机科学的国际会议接受，分别是第57届STOC、第52届ICALP、第40届CCC。前两篇作者是博士生孟泊宁、王踞秋、研究员夏盟佶，第三篇作者还有博士生郑加毅，均来自基础软件与系统实验室前瞻研究室。

任意给定一个布尔变量上的函数集合F，定义Holant_F问题为，求张量网络G的值，其中构成G的点函数形式必须来自F。计数复杂性的研究者，希望证明对每一个F，Holant_F要么易解，在P里，要么难解，是#P难的。在追寻这个终极二分定理的几十年里，沿着不同路线，留下了一连串的精彩二分定理。

其中一个路线允许辅助函数，集合F总包含两个特定的辅助函数——一元函数p₀与p₁时，有已知的二分定理。我们证明了只需任意一个奇数元函数作为辅助函数时的二分定理，中稿CCC。从而，终极二分定理被解决了一部分，剩下了较难的一半：F完全由偶数元函数构成的情形。

分解引理在证明中起到了重要作用。但是分解引理，需要前提条件。我们依靠STOC论文中关于复数值域#EO问题的二分定理，补足了分解引理不成立的情形的二分结论，形成全局有分解引理的表象。#EO作为全体Holant_F问题的子集，也是通往终极二分定理的一条路线，我们的证明先到达中间站#EO^c，然后直达了这条#EO路线的终点站——复数值域#EO，将两个分叉路线——六点模型与ARS权重#EO的二分定理，直接推广合并到终点站了。

但是，以上两个二分定理成果具有重大缺陷。它们不是P与#P难的二分，而是P^NP与#P难的二分。将来判定问题复杂性二分定理的同行，完成判定版的EO问题的二分定理时，这一缺陷会随之自动修复。我们的ICALP论文结果部分修补了此缺陷，找到了两层带来多项式时间算法的非常漂亮的代数结构，但未能完全覆盖住P^NP易解部分的范围。