AF: Small: Classification Program for Counting Problems

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

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.