Atlas home || Conferences | Abstracts | about Atlas

International Conference on Modern Algebra in conjunction with the 17th annual Shanks Lectures
May 21-24, 2002
Vanderbilt University
Nashville, TN, USA

Organizers
Jonathan Farley, Ralph Freese, Matthew Gould, Peter Jipsen, George McNulty, Miklos Maroti, Alexander Ol'shanskii, Steven Tschantz, Constantine Tsinakis, Matthew Valeriote

View Abstracts
Conference Homepage

Constraints, Complexity, and Polymorphisms
by
Peter Jeavons
Oxford University Computing Laboratory

Many natural combinatorial problems can be expressed as "constraint satisfaction problems", so this class of problems has received a lot of attention within Computer Science. Although these problems are NP-hard in general, certain restrictions on the form of the constraints can ensure tractability. By considering the algebra of polymorphisms associated with constraint relations we can translate questions about the computational complexity of this kind of problem into questions about the associated algebra. The talk will provide an introduction to this approach and some results and open questions.

Date received: February 4, 2002

Copyright © 2002 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caig-68.