## 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