Output details
11 - Computer Science and Informatics
Royal Holloway, University of London
An Algebraic Theory of Complexity for Discrete Optimisation
<12>Our earlier work, showing that weighted polymorphisms characterize the complexity of CSP with optimization, produced the understanding of the complexity of optimization which lead to the work in this paper. The initial work, on the complexity of classical CSP languages, has been enormously influential. The natural closure operator for weighted polymorphisms, presented in this paper, provides a theoretical underpinning, allowing the possibility of properly understanding the complexity of optimization. It is already proving to be as influential as the earlier work. For example, it has been a key topic at international meetings in Dagstuhl (2012) and Vancouver (2013)