Counting Problems and Dichotomy Theorems

这个项目研究了计算复杂性理论中的几类计数问题。这些计数问题是自然定义的，包括顶点覆盖、图着色、图匹配等计数问题，这种计数问题的框架称为Holant问题。图同态是图同态的一种特例，它与约束满意问题密切相关。这个项目将带来的一个主要新技术是全息约简和全息算法。这一理论将根据什么函数集(签名)容易处理以及什么导致#P-硬度来发展。霍兰特问题理论的目的是证明复杂性二分法。这些定理对框架中可表示的一类问题中的每个问题都成立，取决于确切的签名集，要么问题在P中是可处理的，要么问题是#P-难的。计算复杂性理论的目的是从根本上理解高效计算的本质。这项研究将明确什么是可计算的，什么是不能有效计算的。全息还原提供了一种新技术。开发的证明技术也可能广泛应用于复杂性理论的相关领域。人们对全息算法和全息约简的概念一直很感兴趣(见《美国科学家》杂志，2008年1-2月)。更清晰地区分什么是有效计算的，什么不是有效计算的，可能也会产生更广泛的影响。新的全息简化和内插很可能为计算复杂性带来新的视角。

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.