Given a collection of constraints, the Constraint Satisfaction Problem (CSP) asks whether they can all be satisfied at once. This simple framework is general enough to capture a wide range of problems, among them propositional satisfiability, graph colouring and systems of linear equations. Fixing the relations allowed in the constraints produces problems of very different complexity, and understanding why has drawn together logic, universal algebra and computational complexity.

In the talk, we will see that the complexity of a CSP is not a property of how its constraints look, but of the structure behind them. This structure can be studied in logic, through the relations it pp-defines, and in algebra, through its polymorphisms, and a Galois connection shows that the two carry the same information. Combined with tools from complexity theory, this view yields complete complexity classifications, both for deciding whether a solution exists and for counting solutions.

We then turn to another aspect of counting, modular counting, where solutions are counted modulo a prime. Here only part of the previous picture survives, and the symmetries of the structure come to the fore. We discuss what is known for graphs, how far it extends to general relational structures, and what remains open.