Algebras and Algorithms

Over the past twenty years a surprising and deep connection has emerged between finite algebraic systems, relational structures, and the computational complexity of an important and vast class of combinatorial problems, known as Constraint Satisfaction Problems (CSPs) [7], [5]. Many familiar problems, such as Boolean satisfiability and graph colorability can be expressed within the CSP framework. While the entire class of CSPs forms an NP-complete class of problems, many naturally occurring subclasses, parametrized by finite relational structures, are tractable [4]. At the beginning of my talk I will present the necessary background from universal algebra [2], [6] to describe the connection between algebra and the CSP and then review the progress that has been made towards settling the Dichotomy Conjecture of Feder and Vardi. They conjecture that the subclass of the CSP parametrized by a given finite relational structure will either lie in the complexity class P or be NPcomplete. Work on the Dichotomy Conjecture has led to some surprising and fundamental results about finite algebras and has motivated research on a number of fronts [1], [9]. In the remainder of my talk I will focus on several results that deal with algorithmic questions about finite algebras. A typical sort of problem, one that is of particular relevance to the CSP, is to determine the complexity of deciding if a given finite algebra has a term operation that satisfies some prescribed set of equations [3], [8].