Constraint satisfaction problems: an algebraic approach to classifying computational complexity
Lecturer: Žaneta Semanišinová / Institute of Algebra, Technical University Dresden, Germany
Date: February 8, 2024
Time: from 11:00 a.m. to 12:00 a.m.
Venue: SJ2P11, Jesenná 5, Košice
Abstract:
The Constraint Satisfiability Problem (CSP) provides a common framework for the study of a number of natural computational problems in different areas of mathematics and computer science, such as the satisfiability problem for logical formulas, the graph colorability problem, or various scheduling problems. In many cases there exist efficient algorithms to solve these problems (in polynomial time), in others we can prove that they are NP-hard and assume that no efficient algorithm exists to solve them. For a fixed relational structure B, CSP(B) is a problem whose input is a finite relational structure A and whose output is the answer to the question of whether there exists a homomorphism from A to B. In this talk, we will focus on an algebraic approach to classifying the complexity of CSP and on results concerning CSP on finite and infinite sets. Finally, we will consider an optimization variant of the CSP, the so-called Valued Constraint Satisfiability Problem.
