计数复杂性的扩展研究

刻画问题的复杂性是计算复杂性最基本的研究问题之一，难解性为设计启发式算法等算法提供理由,有些基础问题的易解性，是经典算法提供的。.本项目探索计数问题的计算复杂性，争取得到所有双限制约束满足计数问题构成的集合的若干子集的计算复杂性二分定理，即集合中的问题要么有多项式时间算法，要么是#P难的。.双限制约束满足计数问题的答案本身就是一个代数量，其定义可以看做是推广到多维数组的矩阵乘法。全息归约方法涉及用矩阵的张量积做线性变换，多项式插值归约方法应用时要找到一组构造，使得用它得到的方程组满秩。从研究方法到具体的二分定理结果都和代数结构有紧密联系。研究过程中一方面加深对全息归约和多项式插值归约两种方法，刻画计数问题的复杂性的能力的认识，开发新的归约方法；另一方面，学习并发展张量秩方面的研究，希望对一些代数结构的认识，能够用在归约中帮助理清问题的复杂性。

本项目支持研究了计数问题的归约方法和计数问题类的复杂性刻画。创造性的使用变定义域的全息归约，给出了一些Holant问题和#CSP问题的复杂性联系。完成了复数值域和模k值域的布尔#CSP问题类和三类Holant问题的复杂性刻画，得到二分定理，即找出了它们中的可以多项式时间计算的问题，并证明了其他问题是#P难的。以上成果发表在SIAM Journal on Computing，Journal of Computer and System Sciences和ACM-SIAM Symposium on Discrete Algorithms等国际刊物和会议。连同其他本项目支持的研究结果，是同期世界范围内计数复杂性领域取得的进展的重要组成部分。