# Mapping the Complexity of Counting

Just as advances in engineering rely on a deep foundational knowledge of physics, so too advances in algorithms and programming
rely on a deep knowledge of the intrinsic nature of computation. Significant progress has been made in understanding the nature
of computation, particularly in the field of **computational complexity,** which aims to discover which computational
problems are feasible and which are inherently infeasible (and why). However, huge theoretical challenges remain: many classes
of problems are poorly understood, including those containing problems arising in practical applications.

The MCC project will enable significant computational advances in a host of application areas through the development of
a comprehensive theory of **counting problems**. These problems are common and important: they arise in practical
applications from diverse fields including statistics, statistical physics, information theory, coding, and machine learning.
In such a problem, a numerical quantity (a weighted sum) is computed, either exactly or approximately. Examples include
computing (or estimating) an integral, a probability, or the expectation of a random variable. Since these counting problems
arise in applications everywhere, it is of fundamental importance to understand their complexity.

We propose a coherent and systematic study of the complexity of counting problems.

The overall objectives of the project are:

- To map out the landscape of computational counting problems (exact and approximate), determining which problems are tractable and which are intractable (quantifying the extent of tractability), and
- To develop complexity characterisations elucidating the features that make counting problems tractable or intractable
(so the goal is not only to discover
**which**problems are tractable, but also to discover a characterisation which tells us**why**).