Ian Payne, Pure Mathematics Department, University of Waterloo
“Determining CSP complexity using universal algebra”
Given a finite relational structure, A, the complexity of the constraint satisfaction problem for A can sometimes be determined using universal algebra. There are several known algebraic conditions on the polymorphism algebra of a structure that imply the NP-completeness of its CSP. The main result in my masters research paper was to prove the equivalence of 6 such conditions. In this talk, I will explain the result, why it is of interest, and prove parts of it as time allows.