Counting Problems and Dichotomy Theorems

计数问题和二分定理

• 批准号: 0914969
• 负责人: Jin-Yi Cai
• 金额: $ 39.73万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0914969&HistoricalAwards=false
• 关键词: Counting; Problems; Dichotomy; Theorems

This project studies several classes of counting problems in computational complexity theory. These counting problems are naturally defined and include such counting problems as vertex covers, graph colorings, graph matchings etc. This framework for counting problems is called Holant Problems. Graph homomorphism is a special case and they are closely related to Constrained Satisfaction Problems. One major new technique this project will bring to bear on these problems is holographic reductions and holographic algorithms.This theory will be developed in terms of what function sets (signatures) are tractable and what lead to #P-hardness. The theory of Holant Problems will aim to prove complexity dichotomy theorems. These theorems assert for every problem in a class of problems expressible in the framework, depending on the exact signature set, either the problem is tractable in P, or the problem is #P-hard.The goal of computational complexity theory is to gain a fundamental understanding of the nature of efficient computation. This study will sharpen the boundary of what is and what is not efficiently computable. Holographic reductions offer a novel technique. The proof techniques developed may also be broadly applicable in related areas of complexity theory.There has been strong interest with the concept of holographic algorithms and holographic reductions (see "American Scientist" magazine, Jan-Feb 2008). A sharper delineation between what is efficiently computable and what is not may also have broader implications. The new holographic reductions together with interpolations are likely to bring new perspectives to computational complexity.

本计画研究计算复杂性理论中的几类计数问题。这些计数问题是自然定义的，包括顶点覆盖，图着色，图匹配等计数问题，这个框架计数问题被称为Holant问题。图同态是一种特殊的情形，它们与约束满足问题密切相关。 这个项目将带来的一个主要的新技术对这些问题的影响是全息约简和全息算法。这个理论将在哪些函数集（签名）是易处理的，以及什么导致#P-硬度方面发展。Holant问题的理论旨在证明复杂性二分法定理。 这些定理断言，对于在框架中可表达的一类问题中的每一个问题，取决于确切的签名集，要么问题在P中是易处理的，要么问题是#P-hard的。计算复杂性理论的目标是从根本上理解有效计算的本质。这项研究将使什么是有效可计算的，什么不是有效可计算的边界更加清晰。 全息缩小提供了一种新颖的技术。全息算法和全息约简的概念引起了人们的强烈兴趣（参见“American Scientist”杂志，2008年1 - 2月）。 在什么是有效可计算的和什么不是有效可计算的之间进行更清晰的划分也可能具有更广泛的含义。新的全息缩减与插值可能会给计算复杂性带来新的视角。