AF: Small: Counting Problems, Holographic Algorithms and Dichotomy Theorems

本计画研究计算复杂性理论中的计数问题。 将调查三个相关领域。(1)自旋系统的近似复杂性。 我们希望在精确理解自旋系统的可近似和不可近似配分函数之间的界限方面取得进展。(2)更好地理解约束满足问题（CSP）的二分法，以及计数问题的相关框架，如图同态和Holant问题。 粗略地说，出现了两种类型的二分法定理。 一种类型是非常明确的，并提供了对易处理性标准的更深入的理解。另一种类型是更无限的，并且通常甚至不清楚易处理性标准是可判定的。 第二种类型的优势在于，从逻辑上讲，它目前的覆盖面更广。 这个项目将研究各种易处理性准则之间的相互关系，具体目标是证明一个可判定的二分法定理，用于在任意固定区域上计数CSP问题的最一般的复加权配分函数。(3)研究基于匹配门的磁畴尺寸大于2的全息算法。 匹配门的可实现性和变换理论已经在域大小为2和复数上的2 × 2矩阵的一般线性群上得到了很好的发展。 但对于更一般的变换群，这是完全未探索的。 这个项目将试图在更一般的群上发展这个理论。 一个具体的目标是证明一个二分法定理的问题超过域大小大于2，提出了一种新的约束函数定义方法，该方法定义的约束函数既可以是一般CSP问题的约束函数，也可以是全息变换和FKT算法的约束函数（《美国科学家》杂志在2008年1 - 2月号上发表了一篇关于这一发展的专题文章。）在什么是有效可计算的或可近似的，什么不是之间的更清晰的划分在计算机科学内外具有更广泛的影响。 在计算机科学中，人们对人工智能有很大的兴趣;大量的工作都围绕着图形模型。这是配分函数的一些形式。 在计算机科学之外，统计物理学有着研究相变的悠久传统，任何可证明的相变与计算复杂性理论之间的联系都将引起人们的极大兴趣。 除了研究生培训，还有大量的计算实验设计的减少，这可能会从事本科生的研究。

This project studies counting problems in computational complexity theory. Three related areas will be investigated.(1) The approximate complexity on spin systems. It is hoped that progress will be made to understand precisely the boundary between approximable and inapproximable partition functions for spin systems.(2) To gain a much better understanding of the dichotomy theorems for Constraint Satisfaction Problems (CSP), and related frameworks of counting problems such as Graph Homomorphisms and Holant Problems. Roughly, there have emerged two types of dichotomy theorems. One type is very explicit and offers a deeper understanding of the tractability criterion. Another type is more infinitary, and often it is not even clear that the tractability criterion is decidable. The strength of the second type is that it currently has a broader coverage in a logical sense. This project will study the interrelationship between various tractability criteria, with the concrete goal of proving a decidable dichotomy theorem for the most general complex-weighted partition functions of counting CSP problems over an arbitrary fixed domain.(3) To study holographic algorithms based on matchgates for domain size greater than two. The realizability and transformation theory of matchgates have already been well developed for domain size two and over the general linear group of 2 by 2 matrices over the complex numbers. But for more general transformation groups this is completely unexplored. This project will attempt to develop the theory over more general groups. A concrete aim is to prove a dichotomy theorem for problems over domain size greater than two, which states that all tractable planar CSP problems are defined by constraint functions that are either tractable for general CSP problems or tractable by a holographic transformation followed by the FKT algorithm using matchgates.There has been strong interest in the novel concept of holographic algorithms (American Scientist magazine had a feature article on this development in the Jan-Feb issue of 2008.) A sharper delineation between what is efficiently computable, or approximable, and what is not has broader impact within computer science and beyond. Within computer science there is a lot of interest in AI; a substantial body of work is centered around graphic models. These are some forms of partition functions. Outside computer science, there is a long tradition in statistical physics to study phase transitions, and any provable link between that and computational complexity theory will be of great interest. In addition to graduate student training, there is also a significant amount of computational experimentation in the design of reductions, which could engage undergraduate students in research.