2018年6月18日，威斯康星大学麦迪逊分校蔡进一教授在静园五院带来了题为“Siegel's Theorem, Edge Coloring, and a Holant Dichotomy”的特邀报告。

　　众所周知，图G上的边可染色问题是经典的NP-完全问题，甚至将问题限制在3-正则图的3-边可染色问题上，仍然是难解的。对于这样的一个判定问题，可以转换成计数问题，即问有多少组染色是合法的。这样的问题往往比原问题来得更加困难，而事实上，对于3-正则图的3-边染色计数问题，可以证明它是Sharp-P-Hard的。

　　对于Sharp-P这样一个神奇而看上去相当庞大的类，其中的层次关系是难以看清楚的。因此，需要引入对于计数复杂性问题的研究框架。这三个框架分别从图同态、CSP问题、Holant问题入手。在本次讲座中，蔡进一教授将3-正则图上的3-边染色计数问题转换到了Holant(G,AD3)问题，并将该问题做了形式上的进一步泛化，得到一系列新的问题Holant(G,f)。对于这类计数问题的复杂度，他给出了一个二分类定理，即倘若G是3-正则图，那么Holant(G,f)要么是多项式可求解的，要么是Sharp-P-Hard的。

　　这个结论的证明本身并不容易。在这个过程中引入了大量的新概念和归约操作，而当大家看到如此庞大的归约网络的时候，心生一惊。但是证明过程中最令人称奇的，当属采用了代数曲线、Siegel定理、Puiseux级数和Galois群这些看似和复杂度理论关系不大的数学工具。基础数学的研究方法对复杂度理论提供了强有力的工具，这一点颇具有启发意义。

　　值得一提的是，这次讲座不但吸引了从事理论工作的老师和对理论计算机感兴趣的同学参加，甚至还有拿到保送资格的高中生来听报告。报告结束后，在场的老师和同学与蔡教授进行了相当久的讨论与思维碰撞。

报告摘要：

What do Siegel's theorem on finiteness of integer solutions have to do with complexity theory? In this talk we discuss a complexity dichotomy theorem for counting problems. Such a dichotomy is a classification of a class of problems into exactly two kinds: those that are polynomial time computable, and those that are #P-hard, and thus intractable. (For logicians, a complexity dichotomy theorem is a kind of restricted anti-Friedberg-Muchnick Theorem.) An example problem in this dichotomy is the problem of counting the number of valid edge colorings of a graph. We will show that an effective version of Siegel's theorem and some Galois theory are key ingredients in the proof of this dichotomy. Along the way we will also meet the Tutte polynomial, medial graphs, Eulerian orientations, Puiseux series, and a certain lattice condition on the (logarithm of) the roots of polynomials with integer coefficients.

Joint work with Heng Guo and Tyson Williams.

报告人简介：

Jin-Yi Cai studied at Fudan University (class of 77). He continued his study at Temple University and at Cornell University, where he received his Ph. D. in 1986. He held faculty positions at Yale University (1986-1989), Princeton University (1989-1993), and SUNY Buffalo (1993-2000), rising from Assistant Professor to Full Professor in 1996. He is currently a Professor of Computer Science and Steenbock Professor of Mathematical Sciences at the University of Wisconsin - Madison.He received a Presidential Young Investigator Award in 1990, an Alfred P. Sloan Fellowship in Computer Science in 1994, a John Simon Guggenheim Fellowship in 1998, and a Morningside Silver Medal of Mathematics in 2004. He also received the Humboldt Research Award for Senior U.S. Scientists. He has been elected a Fellow of ACM, AAAS, and a foreign member of Academia Europaea. He is an Editor of Journal of Computer and Systems Sciences (JCSS), an Editor of International Journal of Foundations of Computer Science, an Associate Editor of Journal of Complexity, an Editor of The Chicago Journal of Theoretical Computer Science, and an Area Editor for International Journal of Software and Informatics. He works in computational complexity theory. He has written and published over 100 research papers.