CONSTRAINT SATISFACTION PROBLEMS AND FINITE ALGEBRAS
Dr Andrei Krokhin, Department of Mathematics and Mechanics, Ural State University, Ekaterinburg, Russia

Abstract: Many natural combinatorial problems can be expressed as Constraint Satisfaction Problems. Given a problem class, one can construct certain finite algebra such that any relation appearing as a constraint belongs to finite power subalgebra system of the algebra. Investigation of such algebras is a new approach leading to a better understanding of the structure of tractable problems.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 28 April 1999.

back