An Algebraic Theory of Complexity for Discrete Optimisation

David A. Cohen, Martin C. Cooper, Páidí Creed, Peter G. Jeavons, Stanislav Živný

Research output: Contribution to journalArticlepeer-review


Discrete optimisation problems arise in many different areas and are studied under many different
names. In many such problems the quantity to be optimised can be expressed as a sum of functions of a restricted
form. Here we present a unifying theory of complexity for problems of this kind. We show that the complexity of a
finite-domain discrete optimisation problem is determined by certain algebraic properties of the objective function,
which we call weighted polymorphisms. We define a Galois connection between sets of rational-valued functions
and sets of weighted polymorphisms and show how the closed sets of this Galois connection can be characterised.
These results provide a new approach to studying the complexity of discrete optimisation. We use this approach
to identify certain maximal tractable subproblems of the general problem, and hence derive a complete classification
of complexity for the Boolean case.
Original languageEnglish
Pages (from-to)1915-1939
Number of pages24
JournalSIAM Journal on Computing
Issue number5
Publication statusPublished - 2013

Cite this