Holant问题的计算复杂性分类研究

FP VS #P is the counting version of P VS NP. By Ladner's theorem, if FP is not equal to #P, then there are counting problems that are neither in FP nor #P-hard. But on the other hand, the dichotomy theorem was proved for counting constraint satisfaction problems(#CSP): For any constraint function set F, #CSP(F) is either in FP or #P-hard. The key observation is that there are no intermediate problems in #CSP as Ladner's theorem predicted. Whether there exist dichotomy theorems in bigger frameworks or not is a hot topic recently. Holant problems is a new framework which covers more counting problems than #CSP. In the project, we will consider the computational complexity classification of Holant problems: (1) characterizing the problems that belong to FP in Holant problems and developing the corresponding polynomial time algorithms; (2) characterizing the #P-hard problems in Holant problems, and developing new methods that reducing some counting problems to known #P-hard counting problems; (3) exploring whether there exists dichotomy theorems in Holant problems or not. Furthermore, we will explore holographic reduction, and the deep relation between computational complexity theory and the mathematical tools involved in the proof from number theory,algebra, geometry, and topology.

FP VS #P问题是P VS NP问题的计数形式。Ladner定理表明，如果FP不等于#P，一定存在既不属于FP，也不是#P-难的计数问题。但在计数约束满足问题中，已证明了二分定理：即计数约束满足问题中的问题要么属于FP，要么是#P-难问题，不存在Ladner定理预测的处于中间状态的问题。在更大的范围内，是否仍可证明二分定理？这在FP VS #P问题的研究中有深刻的意义。Holant问题是一个新的理论框架，涵盖的范围比计数约束满足问题更广。本项目从以下3个方面研究其计算复杂性：（1）刻画Holant问题中属于FP的计数问题，并研究相应的多项式时间算法；（2）刻画Holant问题中的＃P-难计数问题，并发展证明#P-难问题的归约方法和技术；（3）探讨在Holant问题框架下是否存在计算复杂性二分定理。研究全息约化及证明涉及的数论、代数、几何、拓扑等数学工具与计算复杂性理论的内在联系。

本项目研究内容为Holant问题的算法设计与计算复杂性分类，并开展了计算复杂性与机器学习理论基础的交叉研究。.在第一个方面，本项目取得的成果包括：（1）建立了六顶点问题的计算复杂性三分定理，并发现了新的可解类；（2）建立了反向对称的加权欧拉回路计数问题的计算复杂性二分定理，并证明了布尔情形下，加权欧拉回路计数问题涵盖了计数约束满足问题；（3）刻画了Holant问题与量子纠缠的联系，为Holant问题计算复杂性分类的最终解决奠定了基础；（4）完整刻画了分块对称的匹配门函数的结构，从而证明了非布尔情形的计数约束满足问题中不存在非平凡的全息算法。.在第二个方面，本项目取得的成果包括：（1）分析了带动量的梯度下降法的隐式正则性，对最小二乘问题刻画了早停时刻与隐式岭回归正则化的关系；（2）对线性神经网络，探索了深度学习中网络深度与泛化能力的关系。.项目发表期刊和会议论文8篇，包括CCF推荐A类期刊和会议论文5篇，CCF推荐B类会议和期刊论文2篇，CCF推荐C类期刊论文1篇。其中包括SODA，ICALP， SIAM J. Computing，Information and Computation等计算机理论领域的顶级会议和期刊。.本项目在计数问题计算复杂性方面取得的成果具有国际先进性，进一步加深了对难解问题计算复杂性本质的认识和对FP VS #P问题的理解，为Holant问题计算复杂性分类的最终解决奠定了基础。项目组在计算复杂性与机器学习理论基础方面的研究，为深度学习泛化能力的理论解释提供了新的角度。本项目的研究加深了计数问题计算复杂性研究的深度，丰富了计算复杂性领域研究的内容，为理论计算机领域的发展做出了贡献。