The computational complexity of counting

Mark Jerrum

From the introduction: The branch of theoretical computer science known as computational complexity is concerned with quantifying the computational resources required to achieve specified computational goals. Classically, the goal is often to decide the existence of a certain combinatorial structure, for example, whether a given graph G contains a Hamilton cycle. Alternatively, the goal might be to find an occurrence of the structure that is optimal with respect to a certain measure; in the context of the structure ``Hamilton cycle,'' the notorious Travelling Salesman Problem may be cited as an example. Less well studied, and somewhat less well understood, are counting problems, such as determining how many Hamilton cycles a graph G contains. In some areas, such as statistical physics, counting problems arise directly; in many others they appear in the guise of discrete approximations to continuous problems involving multivariate integration. This article aims to sketch the complexity theory of counting, highlighting the ways in which it diverges from that of existence or optimisation.

This paper was presented at the International Congress of Mathematicians, Zürich, August 1994.

LFCS report ECS-LFCS-94-296, July 1994.

Previous | Index | Next