This talk will present the general framework of constraint satisfaction from several different perspectives. This framework can be used to express many different computationalproblems, from timetabling to circuit design and database queries. The complexity of constraint satisfaction problems varies depending on the forms of the constraints allowed, and we describe a very successful approach to determining the complexity of a problem based on the algebraic properties of the constraints. Usinf this approach we show that some very general classes of constraints are tractable.; Finally we discuss how this algebraic approach can be extended to soft constraints, where each tuple of values is associated with some cost and the problem is to find an assignment which minimizes the overall cost. For these problems too we show that there are tractable cases which can be characterized by algebraic properties.

• Thematic program: Fundamentals of Queries and Data Exchange (2005)