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.