AF: Small: Classification Program for Counting Problems

这个项目是对计数问题的计算复杂性的研究。PI的目的是对所谓的和积计算问题的复杂性进行分类。这些计数问题来自计算机科学的各个部分，甚至其他研究领域。它们是自然定义的，包括顶点覆盖、图着色和图匹配等计数问题。这也与统计物理学中研究的问题有很强的联系。在计算复杂性理论中，没有比实现广泛的计算问题的完整分类更高的目标了。这通常是根据P和NP理论来完成的，其中P和NP分别表示通过确定性和非确定性算法在多项式时间内可计算的问题。人们对PI的分类程序有着浓厚的兴趣，尤其是全息算法的概念。在寻找正确的分类公式方面，也有大量的计算实验，为本科生提供了一个参与研究的机会。更清晰地描述什么是可有效计算的，什么不是可有效计算的，将在计算机科学内外产生更广泛的影响。在计算机科学中，人工智能的大量工作都围绕着类似的模型，称为配分函数。在计算机科学之外，统计物理学中有研究配分函数的悠久传统，这项研究为所谓的精确求解模型提供了信息。用更专业的术语来说，这些计算定义为sum_sigma prod_f f |，其中f是局部约束函数，而sigma是对局部变量的赋值。研究这些问题有三个相关的框架。(1)自旋系统或图同态；(2)计数CSP问题；(3)Holant问题。在过去的几年里，以下论点得到了相当多的证据，即大量的乘积和计算可以被精确地分为三类，并在约束函数集上有一个明确的准则：(I)在P中可计算；（II）一般图#P-hard，平面图#P可解；（III）即使对于平面图也是#P-hard。此外，对于自旋系统和计数CSP，类别（II）精确地对应于那些可以用带有匹配门的全息算法解决的问题。但是对于Holant问题，还有一些新的可处理的问题。PI计划证明适用于非对称约束函数的分类定理。如果这可以解决不对称和对称约束函数，它将是一个统一的结果，回答至少自20世纪60年代Kasteleyn时代以来开放的问题。

This project is a study of the computational complexity of counting problems. The PI aims to classify the complexity of problems known as Sum-of-Product computations. These counting problems come from all parts of computer science, and even other fields of study. They are naturally defined and include such counting problems as vertex covers, graph colorings, and graph matchings. There is also a strong connection to problems studied in statistical physics.In computational complexity theory, there is no higher aim than to achieve a complete classification of a wide class of computational problems. This is usually done in terms of the P and NP theory, where P and NP denote problems computable in polynomial time by deterministic and nondeterministic algorithms, respectively. There has been strong interest in the PI's classification program, especially with the concept of holographic algorithms. There is also a significant amount of computational experimentation in the search for the right formulation of the classification, providing an opportunity to engage undergraduate students in research.A sharper delineation between what is or is not efficiently computable will have broader impact within computer science and beyond. Within CS, a substantial body of work in AI is centered around similar models called partition functions. Outside computer science, there is a long tradition in statistical physics to study partition functions, and this study informs the so-called exactly solved models.In more technical terms, these are computations defined as sum_sigma prod_f f | sigma, where the f's are local constraint functions, and the sigmas are assignments to local variables. There are three related frameworks to study these problems.(1) Spin systems or graph homomorphisms,(2) Counting CSP problems, and (3) Holant problems.Over the past several years, the following thesis has gained considerable evidence, namely a large family of Sum-of-Product computations can be classified into exactly three categories with an explicit criterion on the constraint function set:(I) Computable in P;(II) #P-hard for general graphs, but solvable in P for planar graphs; and(III) #P-hard even for planar graphs.Furthermore, for Spin systems and Counting CSP, category (II) corresponds precisely to those problems which can be solved by holographic algorithms with matchgates. But for Holant problems, there are additional novel tractable classes of problems. The PI plans to prove classification theorems that apply to asymmetric constraint functions. If this can be settled for asymmetric as well as symmetric constraint functions, it will be a unifying result, answering questions that are open at least since the time of Kasteleyn in the 1960's.