AF: Small: Classification Program for Counting Problems

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

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.