There is a lot happening on the boundary between universal algebra and computer science. It is not very surprising that algebraists want to have fast algorithms. However, the connection runs in the other direction as well: It turns out that universal algebra is a very good tool for describing the complexity of the Constraint Satisfaction Problem (CSP).
An instance of the CSP asks us to decide if we can assign values to variables in such a way that a list of constraints is satisfied (examples: graph coloring, logical formula satisfiability, Sudoku). If we restrict the sort of constraints to be used, the complexity of solving the CSP can vary from polynomial to NP-complete. We will talk about how to use universal algebra to classify the complexity of many such restricted CSPs.
Universal Algebra Meets Algorithmic Complexity
Dec. 10, 2013 3pm (MATH 350)
PDE/Analysis
Peter Vassiliou (University of Canberra, Australia)
X
ABSTRACT: Gaston Darboux (1842 - 1917) was much occupied with the theory of orthogonal coordinate systems throughout his productive career. Despite his many distinguished researchers as well as vast contributions by others like L. Bianchi (1856 -1928) and G. Lame (1795 - 1870) much remains to be understood and discovered. In this talk I will introduce the basic ideas and then go on to show how the theory of Darboux integrable systems can be used to construct orthogonal coordinate systems. It will be shown that there is a natural relationship between this circle of ideas and certain Einstein metrics as well as a particular completely integrable system, the so called -wave resonant interaction system. A number of open questions will be framed
Universal Algebra Meets Algorithmic Complexity