Counting Problems and Dichotomy Theorems

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

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.