【IJTCS 2020】蔡进一教授谈计数问题复杂性分类的最新成果

  首届国际理论计算机联合大会(International Joint Conference on Theoretical Computer Science,IJTCS)于2020年8月17日-21日在线上举行,主题为“理论计算机科学领域的最新进展与焦点问题”,由北京大学与中国工业与应用数学学会(CSIAM)、中国计算机学会(CCF)、国际计算机学会中国委员会(ACM China Council)联合主办,北京大学前沿计算研究中心承办。  

 

  8月17日,美国威斯康星麦迪逊大学的蔡进一教授带来了题为《计数问题复杂性分类的最新成果》的主题报告。报告由北京大学前沿计算研究中心讲席教授邓小铁主持。

  

 

  首先,蔡老师从图的 H-Coloring(图同态)模型出发,定义了其上的 partition function 与对应的计数问题。这一模型在一些不同领域有重要作用,例如,它能够表示 Ising 模型、hardcore 模型、WR 模型等,而这些模型上的 partition function 是理论物理与理论计算机科学中经常探讨的问题。对于同态矩阵在不同的定义域上(二元,整数,实数,复数等), 报告分别介绍了对应的计数问题的复杂性二分类定理,也就是说,一个问题实例要么是多项式可解的,要么是 #P-Hard 的,并且二分的条件是多项式时间可计算的。上述二分类定理对于限制最大度数的图也是存在的,相关结果将于 FOCS 2020 发表。

 

 

  接下来,蔡老师引入了表示能力强于图同态的模型,即约束可满足计数模型(#CSP),以及表示能力更强的模型,即 Valiant 全息模型(Holant)。在这些计数模型上,他给出了相关的二分类定理。蔡老师特别介绍了最近的一项工作,即在二元定义域、实数值域的约束条件下 Holant 的二分类定理,展示了该项工作与 Bell 态与量子计算的潜在关系。相关工作将于 FOCS 2020 发表。

 

 

  蔡老师着重讨论了与平面图相关的计数问题,以及神奇的 FKT 算法。计数平面图上的完美匹配,可以由 FKT 算法在多项式时间内求解,然而将“平面图”换成一般图,或将“完美匹配”换成匹配,或两个都替换,得到的另外三个问题都是 #P-Hard 的。而 Valiant 提出的 matchgate 与全息算法,拓展了 FKT 算法的应用范围。例如,在最大度数为3的无向平面图上,计数给边定向的方案数目,使得图中没有源点或汇点,这一问题可以由全息变换求解。

 

  在此基础上,蔡老师介绍了在某些定义域与值域下的平面图 Holant 的二分类定理,以及二元定义域上的平面图 #CSP 三分类定理(即,1. 多项式可解的,2. #P-Hard、但是对平面图是多项式可解的,3. 对平面图也是#P-Hard的),并且第2类问题均可以全息归约到 FKT。

 

  为了让听众感受到相关技术是如何应用的,蔡老师展示了其中的一个证明。最后,蔡老师提出了一些开放性问题,回答了有关近似计数的提问,表达了他对相关领域未来的期待。