权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Small: Classification Program for Counting Problems

AF：小：计数问题的分类程序

基本信息

批准号：
1714275
负责人：
Jin-Yi Cai
金额：
$ 45万
依托单位：
University of Wisconsin-Madison
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-09-01 至 2021-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1714275&HistoricalAwards=false
关键词：
AF Small Classification Program Counting

项目摘要

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.

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