计算复杂性问题

Jin-Yi Cai, Zhiguo Fu, Mingji Xia (2018): Complexity classification of the six-vertex model. Information and Computation 259: 130-141

背景：计数复杂性的主要研究对象是包含了#SAT问题的#CSP问题类，以及它的推广Holant问题类。在从布尔#CSP问题类通往布尔Holant问题复杂性刻画的路上，很多介于两者之间的问题集合被研究，起到了开发和增强技术手段，逐步揭示布尔Holant复杂性终极谜团等作用。例如，Holant*、Holant+、HolantC等自然推广，还有借鉴了物理模型的命名方式，例如著名的伊辛模型。

六点模型是物理学家为冰等物质定义的模型，算法和复杂性的研究角度关注，任意取定一个一种只有六个非零值的四元布尔函数F之后，它和二元不等函数构成的张量网络的计算。这种的四元函数对应氧原子，每个氧原子周围有四个氢原子，其中有两个氢原子靠近它，共有四选二即六种情况，其他情况下F的值为零。

科学难题：六点模型对应于用一种四元函数F定义的特殊的Holant计算问题，含有复杂性未知的计算问题，其复杂性刻画是一个需要解决的问题，是通往一般的布尔Holant问题复杂性分类路途上不可跳过的挑战之一。

重要突破： 我们刻画了六点模型中所有问题的复杂性。在其中一种情形的证明中，发现了六点模型涵盖了所有一个二元函数定义的#CSP问题，当把六点模型定义中的任意一个特殊四元函数推广到任意特殊偶数元函数集合时，就涵盖了所有#CSP问题。